Hello Codeforces

As the title states, I think I may have discovered a very nice segment tree variant, but I am not sure whether it corresponds to something already known.

Supported Features And Time Complexity

• Range query (RMQ): O(log n), more precisely O(log r)
• Point update: O(log n)
• Push back (append new element at the end): amortized O(1)
• Pop back (remove last element): O(1)
• 2n+1 memory complexity

These are theoretical algorithmic complexities , not including CPU-level behavior (cache effects, branch prediction, etc.) into account.

Memory

Benchmark (n = 1,000,000 ; q = 10,000,000)

In its optimized version, it has performance comparable to the iterative segment tree, as shown in the benchmark below. You are welcome to copy the benchmark code and test it yourself.

Results identical.

Full Benchmark Source (Iterative Segment Tree vs Forest)

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

struct IterativeSegment {
    int n;
    vector<int> seg;
    IterativeSegment(const vector<int>& arr) {
        n = arr.size();
        seg.resize(2*n);
        for(int i=0;i<n;i++) seg[n+i] = arr[i];
        for(int i=n-1;i>0;i--) seg[i] = max(seg[i<<1], seg[i<<1|1]);
        cout << "seg memory : " << seg.capacity() << '\n';
    }
    void update(int i,int val){
        seg[i+=n] = val;
        for(i>>=1;i>0;i>>=1)
            seg[i] = max(seg[i<<1], seg[i<<1|1]);
    }
    int query(int l,int r){
        int res = INT_MIN;
        for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
            if(l&1) res = max(res, seg[l++]);
            if(r&1) res = max(res, seg[--r]);
        }
        return res;
    }
};

struct ForestSegment {
    int n;
    vector<int> forest;
    inline int ctz(int x){ return __builtin_ctz(x); }
    inline int clz(int x){ return __builtin_clz(x); }

    ForestSegment(const vector<int>& arr){
        n = arr.size();
        forest.resize(n<<1|1);
        build_forest(arr);
    }

    inline void build_forest(const vector<int>& arr){
        for(int i=0;i<n;++i)
            forest[(i+1)<<1] = arr[i];
        for(int len=2;len<=n;len<<=1){
            int half_len = len>>1 , freq = n>>ctz(len) , step = len<<1;
            for(int id=len|1;freq--;id+=step)
                forest[id] = max(forest[id-half_len],forest[id+half_len]);
        }
        cout << "forest memory : " << forest.capacity() << '\n';
    }

    void update_forest(int i , int val){
        int id = i<<1 , lim = n<<1;
        forest[id] = val;
        id += (i&1?1:(--i,-1));
        for(int len = 1 ;id+len<=lim; ){
            forest[id] = max(forest[id-len], forest[id+len]);
            len<<=1;
            id += (i&len?-len:len);
        }
    }

    int query_forest(int ul , int ur){
        int result = INT_MIN;
        int limit = ul-1 , hb , lb , choice;
        while(ul <= ur){
            lb = ur&-ur;
            hb = 1<<(31-clz(ur-limit));
            choice = min(lb,hb);
            result = max(result, forest[(ur<<1)-choice+1]);
            ur -= choice;
        }
        return result;
    }

    void push_forest(int val){
        int id = (++n)<<1;
        forest.resize(id|1,0);
        forest[id] = val;
        for(int loop=ctz(n),len=1;loop--;len<<=1)
            forest[id-=len] = max(forest[id+len],forest[id-len]);
    }

    void pop_forest(){
        forest.resize((--n)<<1|1);
    }
};

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

    int n = 1e6 , q = 1e7;
    vector<int> arr(n);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for(int &x : arr) x = rng()%(1'000'000'000);

    auto t1 = chrono::high_resolution_clock::now();
    IterativeSegment seg(arr);
    auto t2 = chrono::high_resolution_clock::now();
    double seg_build = chrono::duration<double,milli>(t2-t1).count();

    t1 = chrono::high_resolution_clock::now();
    ForestSegment forest(arr);
    t2 = chrono::high_resolution_clock::now();
    double forest_build = chrono::duration<double,milli>(t2-t1).count();

    vector<pair<int,int>> updates(q);
    vector<pair<int,int>> queries(q);
    for(auto &p : updates){
        p.first = rng()%n;
        p.second = rng()%1000000;
    }
    for(auto &p : queries){
        int l = rng()%n, r = rng()%n;
        if(l > r) swap(l,r);
        p = {l,r};
    }

    cout << "Benchmark with n="<<n<<", q="<<q<<"\n";

    t1 = chrono::high_resolution_clock::now();
    for(auto [i,v] : updates) seg.update(i,v);
    t2 = chrono::high_resolution_clock::now();
    double seg_update = chrono::duration<double,milli>(t2-t1).count();

    t1 = chrono::high_resolution_clock::now();
    for(auto [i,v] : updates) forest.update_forest(i+1,v);
    t2 = chrono::high_resolution_clock::now();
    double forest_update = chrono::duration<double,milli>(t2-t1).count();

    t1 = chrono::high_resolution_clock::now();
    long long checksum1 = 0;
    for(auto [l,r]:queries) checksum1 += seg.query(l,r);
    t2 = chrono::high_resolution_clock::now();
    double seg_query = chrono::duration<double,milli>(t2-t1).count();

    t1 = chrono::high_resolution_clock::now();
    long long checksum2 = 0;
    for(auto [l,r]:queries) checksum2 += forest.query_forest(l+1,r+1);
    t2 = chrono::high_resolution_clock::now();
    double forest_query = chrono::duration<double,milli>(t2-t1).count();

    cout << fixed << setprecision(3);
    cout << "IterSegment   build : " << seg_build << " ms\n";
    cout << "ForestSegment build : " << forest_build << " ms\n";
    cout << "IterSegment   update: " << seg_update << " ms\n";
    cout << "ForestSegment update: " << forest_update << " ms\n";
    cout << "IterSegment   query : " << seg_query << " ms\n";
    cout << "ForestSegment query : " << forest_query << " ms\n";
    cout << (checksum1==checksum2 ? "Results identical\n" : "Mismatch!\n");
}

Static version

I would say this is a variant of iterative segment tree , but with forest query core idea

Supported Features And Time Complexity

• Range query (RMQ): O(log n), more precisely O(log r)
• Point update: O(log n)
• memory about 3n in worst case and 2n in best case , it is power of 2 padding on iterative segment tree

Basically the same but better constant and no push back or pop back (you could do pop back freely but push back is not conveniently available in worst case memory)

Benchmark (n = 1,000,000 ; q = 10,000,000)

Benchmark Source Code

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

static inline uint64_t rd() {
    static std::mt19937_64 rng(123456);
    return rng();
}

// ----------------------------------------------------------
//  Segment Tree
// ----------------------------------------------------------
struct Seg1 {
    int n;
    vector<int> seg;
    Seg1(const vector<int>& arr) {
        n = arr.size();
        seg.resize(2*n);
        for(int i=0;i<n;i++) seg[n+i] = arr[i];
        for(int i=n-1;i>0;i--) seg[i] = max(seg[i<<1], seg[i<<1|1]);
        cout << "seg memory : " << seg.capacity() << '\n';
    }
    void update(int i,int val){
        seg[i+=n] = val;
        while(i>>=1)
            seg[i] = max(seg[i<<1], seg[i<<1|1]);
    }
    int query(int l,int r){
        int res = INT_MIN;
        for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
            if(l&1) res = max(res, seg[l++]);
            if(r&1) res = max(res, seg[--r]);
        }
        return res;
    }
};

// ----------------------------------------------------------
//  Statistic Forest
// ----------------------------------------------------------
struct Forest {
    int n , len ;
    vector<int> forest;
    inline int lowbit(int x){ return __builtin_ctz(x); }
    inline int highbit(int x){ return 31-__builtin_clz(x); }
    inline int comb(int a,int b){ return max(a,b); }
    Forest(const vector<int>& a) {
        n = a.size();
        len = 1<<(highbit(n)+1) ;
        forest.resize(len+n+1,0);
        for(int i=0;i<n;i++) forest[len+i] = a[i] ;
        for(int i=(len+n-1)>>1 ; i ;i--) forest[i] = comb(forest[i<<1],forest[i<<1|1]);
        cout << "forest memory : " << forest.capacity() << '\n';
    }
    void update(int i,int v){
        forest[i+=len]=v;
        while(i>>=1)
            forest[i] = comb(forest[i<<1], forest[i<<1|1]);
    }
    int query(int l,int r){
        int res = INT_MIN;
        int k , limit = l , offset = len-1;
        for(l++, r++; l<=r ; r -= 1<<k ){
            k = min(lowbit(r), highbit(r-limit));
            res = comb(res, forest[(r+offset)>>k]);
        }
        return res;
    }
};

// ----------------------------------------------------------
//  MAIN TEST
// ----------------------------------------------------------
int main(){

    int n = 1e6;
    int Q = 1e7;
    int U = 1e7;

    vector<int> a(n);
    for(int i=0;i<n;i++) a[i] = rd() % 1000;

    Seg1   s1(a);
    Forest s2(a);

    // --------------------------------
    //  Generate queries
    // --------------------------------
    vector<pair<int,int>> qs(Q);
    for(int i=0;i<Q;i++){
        int l = rd() % n;
        int r = rd() % n;
        if(l > r) swap(l,r);
        qs[i] = {l,r};
    }

    // --------------------------------
    //  Generate updates
    // --------------------------------
    vector<pair<int,int>> us(U);
    for(int i=0;i<U;i++){
        int pos = rd() % n;
        int val = rd() % 1000000;
        us[i] = {pos,val};
    }

    // ======================================================
    //  BENCH QUERY
    // ======================================================
    long long sum1 = 0, sum2 = 0;

    auto t1 = chrono::high_resolution_clock::now();
    for(int i=0;i<Q;i++){
        auto [l,r] = qs[i];
        sum1 += s1.query(l,r);
    }
    auto t2 = chrono::high_resolution_clock::now();

    auto t3 = chrono::high_resolution_clock::now();
    for(int i=0;i<Q;i++){
        auto [l,r] = qs[i];
        sum2 += s2.query(l,r);
    }
    auto t4 = chrono::high_resolution_clock::now();

    auto tq1 = chrono::duration_cast<chrono::milliseconds>(t2 - t1).count();
    auto tq2 = chrono::duration_cast<chrono::milliseconds>(t4 - t3).count();

    if(sum1 != sum2){
        cout << "QUERY ERROR!\n";
        return 0;
    }

    // ======================================================
    //  BENCH UPDATE
    // ======================================================
    auto t5 = chrono::high_resolution_clock::now();
    for(int i=0;i<U;i++){
        auto [p,v] = us[i];
        s1.update(p,v);
    }
    auto t6 = chrono::high_resolution_clock::now();

    auto t7 = chrono::high_resolution_clock::now();
    for(int i=0;i<U;i++){
        auto [p,v] = us[i];
        s2.update(p,v);
    }
    auto t8 = chrono::high_resolution_clock::now();

    auto tu1 = chrono::duration_cast<chrono::milliseconds>(t6 - t5).count();
    auto tu2 = chrono::duration_cast<chrono::milliseconds>(t8 - t7).count();

    // ======================================================
    //  FINAL CHECK
    // ======================================================
    long long chk1 = 0, chk2 = 0;
    for(int i=0;i<Q;i++){
        auto [l,r] = qs[i];
        chk1 += s1.query(l,r);
        chk2 += s2.query(l,r);
    }

    if(chk1 != chk2){
        cout << "FINAL ERROR AFTER UPDATE!\n";
        return 0;
    }

    // ======================================================
    //  OUTPUT
    // ======================================================
    cout << "n : " << n << " , q : " << Q << " , u : " << U << '\n';
    cout << "Correctness OK\n";
    cout << "IterSegment   query : " << tq1 << " ms\n";
    cout << "ForestSegment query : " << tq2 << " ms\n";
    cout << "IterSegment   update: " << tu1 << " ms\n";
    cout << "ForestSegment update: " << tu2 << " ms\n";

    return 0;
}

Others

• GitHub repository containing other variants (including a more cache-friendly version and a lazy propagation extension):
  https://github.com/Fuvkfis/Forest-of-segment-tree.git
• This idea was originally implemented in November 2025, but it is only being published now due to personal reasons.
• Not sure if its already exist , i did have my own searching but still im not sure . it would be great if you help me verify this