Number of nodes in a segment tree.

implementation
segment-tree

#1

In the following implementation of segment tree, in the case when number of elements in the array for the range query, say A, are n such that n is not a power of 2, then I’m unable to establish that we actually require
2 * (pow(2,ceil((log2(n)))) - 1 nodes of the segment tree.
In which case does the node variable’s value in the following implementation may go past the 2*n-2 ?

https://onlinegdb.com/S1LMjFqCz (solution)

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/range-minimum-query/ (problem statement)


#2

Consider an array of size 10. I will use 1 based indexing as it is convenient with array implementation of ST and Heaps. Refer to the following image, notice that the array[5](0 based) is at tree[24] (1 based index) and not 18. 2*N size is only valid if it was a perfect binary tree. Alternative is to use 4*N size st tree. Read more about it in emaxx ru or gkcs’s channel on youtube.

image here

Image


#3

I understand your pain, I still don’t remember that formula, that’s why I use this code to determine the length of segment tree to declare

int tmp = n;
int count = 0;
while(tmp){
    count+=tmp;
    tmp/=2;
}

This is simple O(log(n)) code. Node causing any problem to anyone. So why not.


#4

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;
}

#5

Nice Method!!


#6

The easiest way to see this, IMHO, is that if n is power of 2 then all the leaf nodes will lie at the same level(level log2(n), considering root at level 0). But if n is not a power of 2, some leaf nodes will lie at the next level, this is due to asymmetry in sibling nodes, one will have greater nodes than other and some of them will only leaf out at the next level. The caveat is the array implementation, since some of the leaf nodes are at next level, you will have to allocate twice as much memory because the implementation demands so, even though some array elements won’t be used.


#7

Thanks pal @kukreja_vlk. Yes, I missed the case when both the segment will have odd nnumber of nodes.