Segment trees
Here I like to discuss cool data structures and algorithms that can computer programmers become much better in what they do :) and its fun to learn and discuss , so lets learn something called 'Segment trees'
Before we talk about what it does , lets discuss whats the need for such a data structure.
Suppose we have an array of N numbers a[1],a[2],....a[N] Now I have two operations that I can perform on this array
- Retrieve the sum of any sub-array between index i..j
- Modify the value of any element a[i]
So whats the complexity of each of these operations
Now lets suppose N is very large then computing the size of each subarray is very costly so we need to think and find a mechanism that helps to reduce the complexity of finding the sum of any sub-array of the given array.
How??
Thats where segment tree comes in....
This is how a segment tree looks for an array int a[]={1,3,5,7,11} of 5 elements
The leaf nodes are the array elements while the internal nodes are merging of index [i..j]
As you can see a node of range [i..j] divides itself into its
left-child - [i..(i+j)/2] and right child [ (i+j)/2 + 1 ...j ]
Each node in the segment tree contains the sum of elements that constitute the segments the node represents.
Eg. sum[0-2] = 1+3+5=9 is shown by the left-child of the root that represents the segment [0-2]
So what did we really gain from this data structure...
Since this is a balanced binary tree- we are breaking the segment into equal halves at each node
The height of the tree is O(logN). Thus if we want to find the sum of elements of any segment [i..j] we can find that in O(logN) time!!!
We have reduced the time complexity from O(N) to O(logN) !!!
Thats cool but there is a downside too, now if i want to change the value of any element then the change in the value of element a[i] will change the sum of every segment that contains the element i,
Thats is all sub-arrays that contain the element a[i]
So we need to update the value of all such nodes in the segment tree whenever an element is modified.
How to do this ... First calculate the change 'c' in element a[i](whether +ve or -ve) and then
simply traverse the path from root to the leaf that shows a[i] and update every node intermediate node adding the value 'c' to the it.
This costs us O(logN)
Thus segment tree gives the following complexities for the 2 operations we wanted to do:
- Retrieve the sum of any sub-array between index i..j - O(logN)
- Modify the value of any element a[i] - O(logN)
The following code constructs a sample segment tree
#include <iostream>
#define f(i,n) for(int i=0;i<n;++i)
#define LL long long
using namespace std;
struct treenode
{
int begin;
int end;
LL sum;
treenode *left,*right;
};
LL construct_segtree(treenode*& root , int begin,int end,int a[])
{
if(root==NULL){
root=new treenode();
root->begin=begin;
root->end=end;
root->left=root->right=NULL;
}
if(begin==end){root->sum=a[begin];return root->sum;}
//else
int mid=(begin+end)/2;
root->sum=construct_segtree(root->left,begin,mid,a)+construct_segtree(root->right,mid+1,end,a);
return root->sum;
}
LL findsum(treenode*& t , int i , int j)
{
if(t->begin==t->end)return t->sum;
if(t->begin==i && t->end==j)return t->sum;
//in between
int mid=(t->begin+t->end)/2;
if(i<=mid&&j<=mid)return findsum(t->left,i,j);
if(i>mid)return findsum(t->right,i,j);
if(i<=mid&&j>mid)return findsum(t->left,i,mid) + findsum(t->right,mid+1,j);
}
void addval(treenode*& t , int i , LL val)
{
//update every node on path
t->sum+=val;
//base case
if(t->begin==t->end)return;
//else
int mid=(t->begin+t->end)/2;
if(i<=mid)addval(t->left,i,val);
else addval(t->right,i,val);
}
int main() {
int a[N];
f(i,N)cin>>a[i];
treenode* root=NULL;
construct_segtree(root,0,N-1,a);
//segment tree constructed
return 0;
}
Hope it helps :)
Comments
Post a Comment