Segment Tree

Segment Tree

Segment_tree

For solving the RMQ problem with size ‘N’ using segment trees we should use an array of size (2*2(Log N + 1))

Child of x is stored at (2*x) and (2*x+1)

#include &ltiostream &gt
using namespace std;

long st[100000];
long a[100000];
void createST(long ind, long from, long to){
	if(from == to){
		st[ind] = from;
		return;
	}
        // build the left child
	createST(2*ind, from, (from + to)/2);
        // build the right child
	createST(2*ind+1, (from + to)/2+1, to) ;
	st[ind] = a[st[2*ind]]<=a[st[2*ind+1]]? st[2*ind] : st[2*ind+1];
}
long query(long ind, long from, long to, long i, long j){
	if(from > j || to<i){
	 	return -1;
	}
	if(i<=from && to<=j){
		return st[ind];
	}
	long r1 = query(ind*2,   from, (from+to)/2, i, j);
	long r2 = query(ind*2+1, (from+to)/2+1, to, i, j);

	if(r1==-1) return r2;
	if(r2==-1) return r1;
	if(a[r1] <= a[r2]) return r1;
	return r2;
}
int main(){
	a[0] = 20;
	a[1] = 10;
	a[2] = 25;
	a[3] = 3;
	a[4] = 100;
	a[5] = 20;
	a[6] = 23;
	a[7] = 55;
	a[8] = 1;
	a[9] = 77;
	createST(1,0,3);
	// example queries
	cout << query(1, 0, 9, 0, 2) << endl; // 1
	cout << query(1, 0, 9, 2, 6) << endl; // 3
	cout << query(1, 0, 9, 6, 9) << endl; // 8
	cout << query(1, 0, 9, 4, 7) << endl; // 5
	cout << query(1, 0, 9, 2, 7) << endl; // 3
	
	return 0;
}