Skip to content

Instantly share code, notes, and snippets.

@varshneydevansh
Created January 1, 2018 12:39
Show Gist options
  • Save varshneydevansh/3c09ba98904963506b5ef23514ec3681 to your computer and use it in GitHub Desktop.
Save varshneydevansh/3c09ba98904963506b5ef23514ec3681 to your computer and use it in GitHub Desktop.
Segment Tree implementation in C++
#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