Well, It’s depend on how you implement segment tree. Let’s say you implemented segment tree in recursive format then, Yes! it will require O(4*N) space in worst case. But if you will implement segment tree in iterative format then it will never use more than O(2*N) space in any case or O(3*N) space if lazy propagation is their. In iterative implementation of segment tree you do not need to allocate space for input because we directly read input in leaf of segment tree as we know that leaf node always represent our input.

If you would like how it’s done you can go through the below code… Happy coding!!

[details=Click to view]

#include< iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int q;
int t[2*N];
void update(int x,int y){
for(t[x+=n]=y; x>1;x>>=1){
t[x>>1] = min(t[x],t[x^1]);
}
}
int query(int l, int r){
int res = 1e8;
for(l+=n,r+=n;l>=1,r>>=1){
if(l&1) res = min(res,t[l++]);
if(r&1) res = min(t[--r],res);
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> q;
for(int i=0;i < n;i++){
cin >> t[i+n];
}
for(int i=n-1;i>0;i--){
t* = min(t[i<<1],t[i<> qt;
if(qt=='q'){
cin >> l >> r;
cout << query(l-1,r) <> l >> r;
update(l-1,r);
}
}
return 0;
}