Segment Tree implementation for Range Maximum Query with Build, Query and Update Operations

Seg_tree.cpp

/*
    Segment Tree implementation for Range Maximum Query 
    Author: Chandan Mittal
*/
#include "stdio.h"
#include "stdlib.h"
#include "limits.h"
#include "math.h"
#include "string.h"
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)    //returns max of 2 values
#define abso(a) (a)>(0)?(a):(-a)
#define lli long long int
using namespace std;

int *tree, tree_size;

//Increment elements within range [i..j] with value: value
void update_tree(int node, int a, int b, int i, int j, int value)
{
    if(a > b || i > b || j < a) //cuurent segment is not within range
        return;

    if(a == b)
    {
        tree[node] += value;
    }
    else
    {
        int mid = (a+b)/2;
        update_tree(2*node, a, mid, i, j, value);
        update_tree(2*node+1, mid+1, b, i, j, value);

        tree[node] = max(tree[2*node], tree[2*node+1]);
    }

}

//Query tree to get maximum element value withhin range[i..j]
int query(int node, int a, int b, int i, int j)
{
    if(a > b || i > b || j < a) //if query out of range
        return -INT_MAX;    //imp here

    if(i <= a && b <= j)
        return tree[node];

    int mid = (a+b)/2;

    int q1 = query(2*node, a, mid, i, j);
    int q2 = query(2*node+1, mid+1, b, i, j);

    int res = max(q1, q2);

    return res;
}

void initialize(int node, int a, int b, int arr[])
{
    if(a > b ) 
        return;  //out of range

    if(a == b)   //leaf node
    {
        tree[node] = arr[a];    //init value
    }
    else
    {
        int mid = (a+b)/2;
        initialize(2*node, a, mid, arr);  //init left child
        initialize(2*node+1, mid+1, b, arr);  //init right child

        tree[node] = max(tree[2*node], tree[2*node+1]); //init root value
    }
}

//Build and initialize Segment Tree
void Build(int arr[], int array_size)
{
    int x = (int)(ceil(log2(array_size))) + 1;
    tree_size = 2*(int)pow(2,x);
//    printf("size is %d\n",tree_size );

    tree = new int[tree_size];
    memset(tree, -1, sizeof(tree));     //initialize whole tree with -1

    initialize(1, 0, array_size-1, arr);
}

//Auxiliary fn to view Segment tree for Better Understanding
void view_tree()
{
    printf("Segment Tree is\n");
    for (int i = 1; i < tree_size ; ++i)
    {
        printf("%d ", tree[i]);
    }
    printf("\n");
}

int main()
{
    int arr[] = {1, 2, -1, 55, -4};
    int n = sizeof(arr)/sizeof(int);

    Build(arr, n);

    view_tree();

    printf("Array is\n");
    for (int i = 0; i < n; ++i)
    {
        printf("%d ",arr[i] );
    }
    printf("\n");

    int i,j, value;
    printf("Enter range>>");
    scanf("%d %d",&i,&j);
    printf("Element with maxm value in range[%d..%d] is %d\n",i,j,query(1,0,n-1,i-1,j-1) );

    printf("Enter range to update>>");
    scanf("%d %d",&i,&j);
    printf("Enter value to add to range [%d..%d]>>",i,j);
    scanf("%d",&value);
    update_tree(1, 0, n-1, i-1, j-1, value);    //update range [i..j]
    printf("Element with maxm value in range[%d..%d] is %d\n",i,j,query(1,0,n-1,i-1,j-1) );    
	return 0;
}