Where have I been wrong in implementation please someone tell me, please?

I am working on this problem for 13+ hours. I read on the discussion that it would require two segment tree and now, I am not getting what is wrong with my code. Though it passes test-cases and I think the main problem must be where I trying to find the median.

#include <bits/stdc++.h>
#define ull unsigned long long int
#define ll long long int
#define P pair
#define V vector
#define S set
#define MS multiset
#define M map
#define MM multimap
#define IT iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
using namespace std;

class SEGMENT_TREE{
ll *arr;
ll n;
ll *tree;
ll treeheight;
public:
  SEGMENT_TREE(ll *A, ll n){
    this->arr = A;
    this->n = n;
    ll tmp = this->n;
    ll count = 0;
    while(tmp){
        count+=tmp;
        tmp/=2;
    }
    this->tree = (ll*)calloc(count*2,sizeof(ll));
    this->treeheight = 0;
  }
  void build_sum_tree(ll node, ll start, ll end);
  void update_sum_tree(ll node, ll start, ll end, ll index, ll value);
  ll query_sum_tree(ll node, ll start, ll end, ll left_index, ll right_index);
  void build_max_tree(ll node, ll start, ll end);
  void update_max_tree(ll node, ll start, ll end, ll index, ll value);
  ll query_max_tree(ll node, ll start, ll end, ll left_index, ll right_index);
  void display_tree();
  void display_array();
};

void SEGMENT_TREE::build_sum_tree(ll node, ll start, ll end){
  if(node > treeheight)treeheight=node;
  if(start == end){
    tree[node] = arr[start];
  }else{
    ll mid = start + (end-start)/2;
    build_sum_tree(2*node,start,mid);
    build_sum_tree(2*node+1,mid+1,end);
    tree[node] = tree[2*node] + tree[2*node+1];
  }
}

void SEGMENT_TREE::update_sum_tree(ll node, ll start, ll end, ll index, ll value){
  if(start == end){
    arr[index] = value;
    tree[node] = value;
  }else{
    ll mid = start + (end-start)/2;
    if(start <= index && index <= mid)update_sum_tree(2*node,start,mid,index,value);
    else update_sum_tree(2*node+1,mid+1,end,index,value);
    tree[node] = tree[2*node] + tree[2*node+1];
  }
}

ll SEGMENT_TREE::query_sum_tree(ll node, ll start, ll end, ll left_index, ll right_index){
  if(right_index < start || left_index > end)return 0;
  if(left_index <= start &&  right_index >= end)return tree[node];
  //If case is none of the above then,
  ll mid = start + (end-start)/2;
  ll p1 = query_sum_tree(2*node,start,mid,left_index,right_index);
  ll p2 = query_sum_tree(2*node+1,mid+1,end,left_index,right_index);
  return p1 + p2;
}
void SEGMENT_TREE::build_max_tree(ll node, ll start, ll end){
  if(node > treeheight)treeheight=node;
  if(start == end){
    tree[node] = start;
  }else{
    ll mid = start + (end-start)/2;
    build_max_tree(2*node,start,mid);
    build_max_tree(2*node+1,mid+1,end);
    tree[node] = (arr[tree[2*node]] > arr[tree[2*node+1]])?tree[2*node]:tree[2*node+1];
  }
}

void SEGMENT_TREE::update_max_tree(ll node, ll start, ll end, ll index, ll value){
  if(start == end){
    arr[index] = value;
    tree[node] = index;
  }else{
    ll mid = start + (end-start)/2;
    if(start <= index && index <= mid)update_max_tree(2*node,start,mid,index,value);
    else update_max_tree(2*node+1,mid+1,end,index,value);
    tree[node] = (arr[tree[2*node]] > arr[tree[2*node+1]])?tree[2*node]:tree[2*node+1];
  }
}

ll SEGMENT_TREE::query_max_tree(ll node, ll start, ll end, ll left_index, ll right_index){
  if(right_index < start || left_index > end)return 0;
  if(left_index <= start &&  right_index >= end)return tree[node];
  //If case is none of the above then,
  ll mid = start + (end-start)/2;
  ll p1 = query_max_tree(2*node,start,mid,left_index,right_index);
  ll p2 = query_max_tree(2*node+1,mid+1,end,left_index,right_index);
  if(p1 == 0)return p2;
  if(p2 == 0)return p1;
  return (arr[p1]>arr[p2])?p1:p2;
}

void SEGMENT_TREE::display_tree(){
  for(ll i = 1; i <= treeheight; ++i){
    cout << tree[i] << " ";
    if(i%20 == 0)cout << endl;
  }
}
void SEGMENT_TREE::display_array(){
  for(ll i = 1; i <= n; ++i){
    cout << arr[i] << " ";
    if(i%20 == 0)cout << endl;
  }
}

ll gcd(ll a, ll b){
  if(a == 0)return b;
  return gcd(b%a,a);
}

ll lcm(ll a, ll b){
  return (a*b)/gcd(a,b);
}

int main(){
  FAST
  ll t;
  cin >> t;
  while(t--){
    ll n,q;
    cin >> n >> q;
    ll *arr = new ll[n+1];
    for(ll i = 1; i <= n; ++i)cin >> arr[i];
    SEGMENT_TREE mode(arr,n);
    SEGMENT_TREE median(arr,n);
    mode.build_max_tree(1,1,n);
    median.build_sum_tree(1,1,n);
    while(q--){
      ll a,b,c;
      cin >> a >> b >> c;
      if(a == 2){
        mode.update_max_tree(1,1,n,b,c);
        median.update_sum_tree(1,1,n,b,c);
      }else{
        ll mo = mode.query_max_tree(1,1,n,b,c);
        ll elements = median.query_sum_tree(1,1,n,b,c);
        ll tmp = elements;
        ll med;
        if(elements%2==0)elements++;
        elements/=2;
        while(elements-arr[b] > 0){
          elements-=arr[b++];
        }
        med = b;
        if(tmp%2 == 0){
          if(elements - arr[b]<1){
            b++;
            while(arr[b]==0)b++;
          }
          med+=b;
          med/=2;
        }
        cout << lcm(med,mo) << endl;
      }
    }
  }
  return 0;
}