Segment Tree - Range Minimum Query

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <climits>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>

using namespace std;

#define REP(i,n) for(__typeof(n) i=0; i<(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define RFOR(i,a,b) for(__typeof(b) i=(a); i>(b); i--)
#define RESET(t,value) memset((t), value, sizeof(t))

#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

#define PI acos(-1.0)
#define INF (1<<30)
#define eps 1e-8
#define pb push_back
#define ppb pop_back
#define pii pair<int, int>
#define G struct Graph

typedef long long int64;
typedef unsigned long long ui64;
typedef long double d64;

template< class T > T gcd(T a, T b) {
    return (b != 0 ? gcd<T>(b, a%b) : a);
}
template< class T > T lcm(T a, T b) {
    return (a / gcd<T>(a, b) * b);
}
template< class T > void setmax(T &a, T b) {
    if(a < b) a = b;
}
template< class T > void setmin(T &a, T b) {
    if(b < a) a = b;
}

vector < int > pset (1000);
void initSet(int _size) {
    pset.resize(_size);
    FOR(i,0,_size-1) pset[i] = i;
}
int findSet(int i) {
    return (pset[i]== i)? i : (pset[i] = findSet(pset[i]));
}
void unionSet(int i,int j) {
    pset[findSet(i)]=findSet(j);
}
bool isSameSet(int i,int j) {
    return findSet(i)==findSet(j);
}

#define Max 100
/**
 *@code starts
**/

/*
Segment Tree Library
The segment tree is stored like a heap array
*/

#define RANGE_SUM 0
#define RANGE_MIN 1
#define RANGE_MAX 2

vector <int> segment_tree;

void init_segment_tree(int N) { // if original array size is N

    // the required segment tree array length is 2*2^(floor(log2(N))) + 1;
    int length = (2 * pow(2.0, floor(log((double)N) / log(2.0)) + 1 ) );
    // resize the vector and fill with zero
    segment_tree.resize(length, 0);
}

void build_segment_tree( int code, int A[], int node, int begin, int end ) {
    if (begin == end) {
        if (code == RANGE_SUM) {
            //store value of the cell
            segment_tree[node] = A[begin];
        } else {
            //if RANGE_MIN/MAX store index
            segment_tree[node] = begin;
        }
    } else {
        //recursively compute the values in the left and right subtrees
        int leftIndx = 2 * node, rightIndx = 2 * node + 1;
        build_segment_tree(code, A, leftIndx, begin, (begin + end) / 2);
        build_segment_tree(code, A, rightIndx, (begin + end) / 2 + 1, end);
        int lContent = segment_tree[leftIndx], rContent = segment_tree[rightIndx];

        if (code == RANGE_SUM) { // make this segment contains sum of left and right subtree
            segment_tree[node] = lContent + rContent;
        } else { // code == RANGE_MIN/MAX
            int lValue = A[lContent], rValue = A[rContent];
            if (code == RANGE_MIN) {
                segment_tree[node] = (lValue <= rValue) ? lContent : rContent;
            } else {
                segment_tree[node] = (lValue >= rValue) ? lContent : rContent;
            }

        }

    }

}

//[r1,r2] = [r1, (r1+r2)/2] , [(r1+r2)/2 + 1, r2]

int query(int code, int A[], int node, int begin, int end, int i, int j) {
    // i = left index, j = right index
    if (i > end || j < begin) {
        // if the current interval does not intersect query interval
        return -1;
    }

    if (begin >= i && end <= j) {
        // if the current interval is inside query interval
        return segment_tree[node];
    }

    // compute the minimum position in the left and right part of the interval
    int pos1 = query(code, A, 2 * node, begin, (begin + end) / 2, i, j);
    int pos2 = query(code, A, 2 * node + 1, (begin + end) / 2 + 1, end, i, j);

    // return the position where the overall minimum is
    if(pos1 == -1) return pos2; // can happen if we try to access segment outside query
    if(pos2 == -1) return pos1; // same as above

    if (code == RANGE_SUM) {
        return pos1 + pos2;
    } else if(code == RANGE_MIN) {
        return (A[pos1] <= A[pos2]) ? pos1 : pos2;
    } else return (A[pos1] >= A[pos2]) ? pos1 : pos2;
}

int main() {
    int A[] = {8, 7, 3, 9, 5, 1, 10};
    init_segment_tree(7);
    build_segment_tree(RANGE_MIN, A, 1, 0, 6);
    cout << "RMQ(1, 3) : " << query(RANGE_MIN, A, 1, 0, 6, 1, 3);
    return EXIT_SUCCESS;
}