Bottom-Up Segment Tree — Simple Iterative Implementation

Introduction

A Segment Tree is a useful data structure for answering range queries and performing point updates efficiently.

There are many ways to implement a Segment Tree. The most common implementation uses recursion, but it is also possible to implement the entire tree bottom-up and iteratively, without using recursion at all.

This post presents a simple bottom-up implementation for range minimum queries and point updates.

The main idea is to store the whole tree in an array and use the following relationships:

parent = i
left child = 2 * i
right child = 2 * i + 1

1. Tree Structure

Let n2 be the smallest power of 2 such that:

n2 >= n

We store all elements of the original array in the leaves, starting from index n2.

For example, if:

n2 = 8

the leaves are:

node[8], node[9], ..., node[15]

The root is node[1].

For every internal node:

node[i] = min(node[2 * i], node[2 * i + 1])

Therefore, node[i] stores the minimum value of the entire segment represented by that node.

2. Build

First, we find the smallest power of 2 greater than or equal to n:

n2 = 1;

while(n2 < n)
    n2 *= 2;

Then we put the elements of the array into the leaves:

for(int i= 0; i< n; i++)
    cin >> node[n2 + i];

If n is not a power of 2, the remaining leaves are filled with LLONG_MAX.

This is important because we are calculating minimums, so these extra elements must not affect the answer.

After that, we calculate all internal nodes from bottom to top:

for(int i= n2 - 1; i>= 1; i--)
    node[i] = min(node[2 * i], node[2 * i + 1]);

For example, suppose:

a = [5, 2, 7, 1]

Then:

node[4] = 5
node[5] = 2
node[6] = 7
node[7] = 1

Then we calculate:

node[2] = min(5, 2) = 2
node[3] = min(7, 1) = 1
node[1] = min(2, 1) = 1

Therefore, node[1] contains the minimum value of the whole array.

3. Update

Suppose we want to change:

a[index] = value

First, we move from the array index to its corresponding leaf:

index += n2;

Then we update that leaf:

node[index] = value;

Only the ancestors of this leaf can be affected.

Therefore, we move upward toward the root:

index /= 2;

while(index >= 1){
    node[index] = min(node[2 * index], node[2 * index + 1]);
    index /= 2;
}

At every step, we recalculate the value of the current node using its two children.

Thus, after the update, every node on the path from the changed leaf to the root contains its correct minimum again.

4. Query

The query function calculates the minimum value in the half-open range:

[l, r)

First, we move both endpoints to the leaf level:

l += n2;
r += n2;

Now [l, r) represents the part of the tree that still has to be processed.

At every level, we check both endpoints.

Left endpoint

If:

l % 2 == 1

then l is a right child.

Therefore, the whole segment represented by node[l] is completely inside the query range.

So we can directly add it to the answer:

ans = min(ans, node[l]);
l++;

There is no need to visit its children because the entire segment is already contained in the query range.

Right endpoint

If:

r % 2 == 1

then r is the right boundary of the current range.

Therefore, node[r - 1] is the last complete segment contained in the query range.

We include it:

r--;
ans = min(ans, node[r]);

After processing both sides, we move both endpoints one level upward:

l /= 2;
r /= 2;

We repeat this process until:

l >= r

At that point, every part of the requested range has been processed, so ans is the minimum value of the whole range.

5. Why is the Query O(log n)?

The height of the Segment Tree is:

log2(n)

At each level, we can process at most:

1 node from the left side
+
1 node from the right side

Therefore, at most:

2 log2(n)

nodes are processed.

So:

O(2 log n) = O(log n)

This gives a very simple way to see why the query is O(log n).

6. Complexity

The main advantage of this implementation is that it is completely iterative.

There is no recursion in either the update or the query.

We simply move between a node and its parent using:

i / 2

and between a node and its children using:

2 * i
2 * i + 1

This makes the implementation compact and keeps the structure of the Segment Tree explicit.

7. Complete Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N= 1e6+ 10;

ll node[2* N];
int n2;

void build(int n){
    n2= 1;

    while(n2< n)
        n2*= 2;

    for(int i= 0; i< n; i++)
        cin>> node[n2+ i];

    for(int i= n; i< n2; i++)
        node[n2+ i]= LLONG_MAX;

    for(int i= n2- 1; i>= 1; i--)
        node[i]= min(node[2* i], node[2* i+ 1]);
}

void update(int index, ll value){
    index+= n2;
    node[index]= value;

    index/= 2;

    while(index>= 1){
        node[index]= min(node[2* index], node[2* index+ 1]);
        index/= 2;
    }
}

ll query(int l, int r){
    l+= n2;
    r+= n2;

    ll ans= LLONG_MAX;

    while(l< r){
        if(l% 2== 1){
            ans= min(ans, node[l]);
            l++;
        }

        if(r% 2== 1){
            r--;
            ans= min(ans, node[r]);
        }

        l/= 2;
        r/= 2;
    }

    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin>> n>> q;

    build(n);

    while(q--){
        int t;
        cin>> t;

        if(t== 1){
            int index;
            ll value;

            cin>> index>> value;

            update(index, value);
        }
        else{
            int l, r;
            cin>> l>> r;

            cout<< query(l, r)<< '\n';
        }
    }

    return 0;
}

Conclusion

This implementation provides a simple way to build and use a Segment Tree without recursion.

The key idea is to store the leaves consecutively, build the internal nodes from bottom to top, and perform both updates and queries by moving upward through the tree.

For range minimum queries:

Build  : O(n)
Update : O(log n)
Query  : O(log n)

The query complexity can be seen directly from the fact that at every level we process at most two nodes, giving at most 2 log n processed nodes.