Segment Tree or RMQ
3 min readJul 6, 2020
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.
- we can split the [L, R] to two nodes from the mid, specifically, we are splitting in this way, M = L+(R-L)/2, [L, M], [M+1, R].
- As the tree is built by splitting the range from the middle, the tree is balanced.
- If we give the root node index as 1 and keep on increasing the index by one if we do the pre-order traversing, then suppose that we have a node, left, child and right child. left_child_idx = parent_node_idx *2, right_child_idx = parent_node_idx*2+1, parent_node_idx = left or right_idx /2
- If we are going to do the range query, then each layer we need at most two nodes. If we need more than 2 nodes, say 3 nodes, we CAN find a parent node that already includes two nodes in this level. Hence, the complexity of each range query will be O(log N).
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 sizevoid 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;
}
