Created
January 1, 2018 12:39
-
-
Save varshneydevansh/3c09ba98904963506b5ef23514ec3681 to your computer and use it in GitHub Desktop.
Segment Tree implementation in C++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <math.h> | |
#include <vector> | |
#include <cstdio> | |
using namespace std; | |
#define RSUM 0 | |
#define RMIN 1 | |
#define RMAX 2 | |
vector<int> mytree; | |
void init_tree(int n){ | |
int length = (int)(2*pow(2.0,floor((log((double)n)/log(2.0))+1))); | |
mytree.resize(length,0); | |
} | |
void build(int code, int A[],int node, int beg, int end) | |
{ | |
if(beg == end) | |
{ | |
if(code == RSUM) mytree[node] = A[beg]; | |
else mytree[node] = beg; | |
} | |
else | |
{ | |
int lndx = 2 * node, rndx = 2 * node +1; | |
build(code, A, lndx, beg, (beg+end)/2); | |
build(code, A, rndx, (beg+end)/2 + 1, end); | |
int lcntnt = mytree[lndx], rcntnt = mytree[rndx]; | |
if(code == RSUM){mytree[node] = lcntnt + rcntnt;} | |
else{ | |
int lval = A[lcntnt], rval = A[rcntnt]; | |
if (code == RMIN) mytree[node] = (lval <= rval) ? lcntnt : rcntnt; | |
else mytree[node] = (lval >= rval) ? lcntnt : rcntnt; | |
} | |
} | |
} | |
int query(int code, int A[], int node, int b, int e, int i, int j) { | |
if (i > e || j < b) return -1; | |
if (b >= i && e <= j) return mytree[node]; | |
int p1 = query(code, A, 2 * node , b , (b + e) / 2, i, j); | |
int p2 = query(code, A, 2 * node + 1, (b + e) / 2 + 1, e , i, j); | |
if (p1 == -1) return p2; | |
if (p2 == -1) return p1; | |
if (code == RSUM) return p1 + p2; | |
else if (code == RMIN) return (A[p1] <= A[p2]) ? p1 : p2; | |
else return (A[p1] >= A[p2]) ? p1 : p2; | |
} | |
int main() { | |
int n; | |
cout << "Enter the no. of elements :\n"; | |
cin >> n; | |
int A[n]; | |
init_tree(7); | |
cout << "Enter the elements : \n"; | |
for(int i = 0; i < n; i++) | |
{ | |
cin >> A[i]; | |
} | |
build(RMIN, A, 1, 0, n-1); | |
int q, l, r; | |
cout << "Enter no. of queries"; | |
cin >> q; | |
while(q--) | |
{ | |
cout << "Enter l and r " << endl; | |
cin >> l >> r; | |
printf("%d\n",query(RMIN, A, 1, 0, n-1, l, r) ); // answer | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment