An example of a segment tree.

Segment tree can be used to do the range max/min query(RMQ).

Some properties of the segment tree are:

  • The relationship between different nodes is either including or included (such as parent node to child node) or totally no overlapping.

Sample code from HERE:

/*Author:Hacker_vision*/
#include<bits/stdc++.h>
using namespace std;
const int _max = 50000 + 10;
int n,a[_max],x,y;
char s[20];
struct segTree{
int lc,rc;//left child, right child
int sum;
}segTree[_max*4];//segment tree usually is 4 times the original size
void build(int root,int L,int R){//build the segment tree O(logN)
segTree[root].lc=L;
segTree[root].rc=R;
if(L==R){
segTree[root].sum=a[L];
return;
}
int mid = (L + R) >> 1;
build(root<<1,L,mid);
build(root<<1|1,mid+1,R);
segTree[root].sum=segTree[root<<1].sum+segTree[root<<1|1].sum;//update parent
}
void update(int root,int pos,int add){//update O(logN)
if(segTree[root].lc==segTree[root].rc){
segTree[root].sum += add;
return ;
}
int mid = (segTree[root].lc + segTree[root].rc) >> 1;
if(pos <= mid) update(root<<1,pos,add);
else update(root<<1|1,pos,add);
//backtracking
segTree[root].sum=segTree[root<<1].sum+segTree[root<<1|1].sum;
}
int query(int root,int L,int R){//range query,O(logN)
if(segTree[root].lc==L && segTree[root].rc == R) return segTree[root].sum;
int mid = (segTree[root].lc + segTree[root].rc)>>1;
if(R <= mid) return query(root<<1,L,R);
else if(mid < L) return query(root<<1|1,L,R);
else return query(root<<1,L,mid)+query(root<<1|1,mid+1,R);
}
int main(){
//freopen("input.txt","r",stdin);
int T;cin>>T;int cnt=1;
while(T--){
scanf("%d",&n);
for( int i = 1; i <= n; ++ i) scanf("%d",a+i);
build(1,1,n);
printf("Case %d:\n",cnt++);
while(scanf("%s",s)==1&&strcmp(s,"End")){
scanf("%d%d",&x,&y);
if(strcmp(s,"Add")==0) update(1,x,y);
else if(strcmp(s,"Sub")==0) update(1,x,-y);
else if(strcmp(s,"Query")==0) printf("%d\n",query(1,x,y));
}
}
return 0;
}

Another version code can be found HERE

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=50050;
int t,N;
int tr[MAX<<4];
void re(int x)
{
tr[x]=tr[x*2]+tr[x*2+1];
}
void build(int st,int ed,int node)
{
if(st==ed)
{
scanf("%d",&tr[node]);
return;
}
int mid=(st+ed)>>1;
build(st,mid,node<<1);
build(mid+1,ed,(node<<1)+1);
re(node);
}
void update(int st,int ed,int node,int id,int val)
{
if(st==ed)
{
tr[node]+=val;
return;
}
int mid=(st+ed)>>1;
if(id<=mid)
{
update(st,mid,node<<1,id,val);
}
else
{
update(mid+1,ed,node<<1|1,id,val);
}
re(node);
}
int query(int st,int ed,int node,int l,int r)
{
if(r<st||l>ed) return 0;
else if(st>=l&&ed<=r) return tr[node];
int mid=(st+ed)>>1;
int l_sum=query(st,mid,node<<1,l,r);
int r_sum=query(mid+1,ed,node<<1|1,l,r);
return l_sum+r_sum;
}
int main()
{
scanf("%d",&t);
for(int k=1;k<=t;k++)
{
scanf("%d",&N);
printf("Case %d:\n",k);
build(1,N,1);
char op[10];
while(scanf("%s",op))
{
if(op[0]=='E')
{
break;
}
int i,j;
scanf("%d %d",&i,&j);
if(op[0]=='A')
{
update(1,N,1,i,j);
}
if(op[0]=='S')
{
update(1,N,1,i,-j);
}
if(op[0]=='Q')
{
cout<<query(1,N,1,i,j)<<endl;
}
}
}
return 0;
}

Reference

[1]https://www.bilibili.com/video/BV11t411x7ZG

[2]https://en.wikipedia.org/wiki/Range_minimum_query

Data Scientist/MLE/SWE @takemobi