### 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)↵
[spoiler=Benchmark code]↵
↵
```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");↵
}↵
```↵
[/spoiler]↵
↵
###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↵
[spoiler=Benchmark code]↵
↵
```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;↵
}↵
```↵
↵
[/spoiler]↵
↵
## 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
↵
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)↵
[spoiler=Benchmark code]↵
↵
```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");↵
}↵
```↵
[/spoiler]↵
↵
###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↵
[spoiler=Benchmark code]↵
↵
```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;↵
}↵
```↵
↵
[/spoiler]↵
↵
## 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



