Posts Tagged ‘structure’
Segment Trees
A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmical time. We define the segment tree for the interval [i, j] in the following recursive manner:
- the first node will hold the information for the interval [i, j]
- if i<j the left and right son will hold the information for the intervals [i, (i+j)/2] and [(i+j)/2+1, j]
See the picture below to understand more :
We can use segment trees to solve Range Minimum/Maximum Query Problems (RMQ). The time complexity is T(N, log N) where O(N) is the time required to build the tree and each query takes O(log N) time. Here’s a C++ template implementation :
#include<iostream> using namespace std; #include<math.h> template<class T> class SegmentTree { int *A,size; public: SegmentTree(int N) { int x = (int)(ceil(log2(N)))+1; size = 2*(int)pow(2,x); A = new int[size]; memset(A,-1,sizeof(A)); } void initialize(int node, int start, int end, T *array) { if (start==end) A[node] = start; else { int mid = (start+end)/2; initialize(2*node,start,mid,array); initialize(2*node+1,mid+1,end,array); if (array[A[2*node]]<= array[A[2*node+1]]) A[node] = A[2 * node]; else A[node] = A[2 * node + 1]; } } int query(int node, int start, int end, int i, int j, T *array) { int id1,id2; if (i>end || j<start) return -1; if (start>=i && end<=j) return A[node]; int mid = (start+end)/2; id1 = query(2*node,start,mid,i,j,array); id2 = query(2*node+1,mid+1,end,i,j,array); if (id1==-1) return id2; if (id2==-1) return id1; if (array[id1]<=array[id2]) return id1; else return id2; } }; int main() { int i,j,N; int A[1000]; scanf("%d",&N); for (i=0;i<N;i++) scanf("%d",&A[i]); SegmentTree<int> s(N); s.initialize(1,0,N-1,A); while (scanf("%d%d",&i,&j)!=EOF) printf("%d\n",A[s.query(1,0,N-1,i-1,j-1,A)]); }
Resources:
NJOY!
-fR0D