Is this a new segment tree variant or a rediscovery ?
Difference between en3 and en4, changed 114 character(s)
### 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↵
↵
| Structure      | Memory (units) |↵
|---------------|----------------|↵
| IterSegment   | 2000000       |↵
| ForestSegment | 2000001       |↵
↵
## 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.↵
↵
| Operation | IterSegment (ms) | ForestSegment (ms) |↵
|-----------|------------------|--------------------|↵
| Build     | 2.723            | 3.801              |↵
| Update    | 450.598          | 1065.326           |↵
| Query     | 966.699          | 541.838            |↵
↵
**Results identical.**↵
↵
## Full Benchmark Source (Iterative Segment Tree vs Forest)↵
<details>↵
<summary>Benchmark code</summary>↵
↵
```cpp↵
↵
#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");↵
}↵
</details> ```↵
↵
###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)↵
↵
| Structure     | Memory    | Query (ms) | Update (ms) |↵
| ------------- | --------- | ---------- | ----------- |↵
| IterSegment   | 2,000,000 | 1044       | 415         |↵
| ForestSegment | 2,048,577 | 816        | 336         |↵
↵
##Benchmark Source Code↵
<details>↵
<summary>Benchmark code</summary>↵
↵
```cpp↵
#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;↵
}↵
</details> ```↵
↵
## 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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English quynhnhu.111207 2026-02-15 11:39:42 114
en3 English quynhnhu.111207 2026-02-15 11:38:49 116
en2 English quynhnhu.111207 2026-02-15 11:36:28 2 Tiny change: 'mplexity\nThese ar' -> 'mplexity\n\nThese ar'
en1 English quynhnhu.111207 2026-02-15 11:35:55 13330 Initial revision (published)