Segment trees range maximum query: Finding maximum element in given range

Segment Tree: 

Program:

#include <iostream>
#include <vector>
using namespace std;
const int M = 100000; // maximum size of input array
vector<long> v(M), tree(M * 4); // allocating size for segment tree and array
void build(long node, long a, long b) // to construct segment tree
{
 if (a > b) 
     return;
 if (a == b) 
 {
  tree[node] = v[a];
  return;
 }
 build(node * 2 + 1, a, (a + b) / 2);
 build(node * 2 + 2, (a + b) / 2 + 1, b);
 if (tree[node * 2 + 1] > tree[node * 2 + 2])
  tree[node] = tree[node * 2 + 1];
 
 else
  tree[node] = tree[node * 2 + 2];
}
void update(long node, long a, long b, long x, long y) // to update segment tree
{
 if (a > b) 
     return;
 if (a == b) {
  v[x] = y;
  tree[node] = y;
 }
 else
 {
  long mid = (a + b) / 2;
  if (x <= mid) update(node * 2 + 1, a, mid, x, y);
  else update(node * 2 + 2, mid + 1, b, x, y);
  if (tree[node * 2 + 1] > tree[node * 2 + 2])
   tree[node]= tree[node * 2 + 1];
  else 
   tree[node] = tree[node * 2 + 2];
 }
}
long query(long node, long a, long b, long l, long r) // to query segment tree 
{
 if (a > b || a > r || b < l)
 {
  long temp;
  temp = -9223372036854775807;
  return temp;
 }
 if (a >= l && b <= r) 
     return tree[node];
 long p1 = query(node * 2 + 1, a, (a + b) / 2, l, r);
 long p2 = query(node * 2 + 2, (a + b) / 2 + 1, b, l, r);
 if (p1 > p2) 
     return p1;
 else 
     return p2;
}
int main() 
{
 long n, q, l, r, i, x, y, ch;
 cin >> n >> q;                  // reading number of elements and number of queries
 for (i = 0; i < n; i++) 
  cin >> v[i];                // reading input array

 build(0, 0, n - 1);

 while (q--) 
 {
  cin >> ch;
  if (ch == 1)
  {
   cin >> x >> y;
   update(0, 0, n - 1, x, y);
  }
  else
  {
   cin >> l >> r;
   cout<<query(0,0,n-1,l,r);
  }
 }
return 0;
}

Input :

6             --number of array elements

3             --number of queries

-2  4  2  -1  7  5             array elements

2 0 3       -maximum element in index between 0 and 3

1 4 2       -update 4th index element to 2

2 0 5       -maximum element in index between 0 and 5

Output:45

=========================================================================

Problem: http://codeforces.com/problemset/problem/339/D

Solution using Segment trees: 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int M = 131073;
vector<long> v(M);
vector<pair<long, long>> tree(M * 4);
void build(long node, long a, long b) {
 if (a > b) return;
 if (a == b) 
 {
  tree[node].first = v[a];
  tree[node].second=1;
  return;
 }
 build(node * 2 + 1, a, (a + b) / 2);
 build(node * 2 + 2, (a + b) / 2 + 1, b);
 tree[node].second = tree[2*node+1].second+1;
 if (tree[node].second&1)
  tree[node].first = tree[node * 2 + 1].first ^ tree[node * 2 + 2].first;
 else
     tree[node].first = tree[node * 2 + 1].first | tree[node * 2 + 2].first;
}
void update(long node, long a, long b, long x, long y) 
{
 if (a > b)
     return;
 if (a == b)
 {
  tree[node].first = y;
 }
 else 
 {
  long mid = (a + b) / 2;
  if (a<=x && x <= mid) 
      update(node * 2 + 1, a, mid, x, y);
  else 
      update(node * 2 + 2, mid + 1, b, x, y);
  if (tree[node].second&1)
      tree[node].first = tree[node * 2 + 1].first ^ tree[node * 2 + 2].first;
     else
         tree[node].first = tree[node * 2 + 1].first | tree[node * 2 + 2].first;
 }
}

int main() 
{
 long n, q, l, r, i, x, y, ch;
 cin >> n >> q;
 n=pow(2,n);
 for (i = 0; i < n; i++) 
  cin >> v[i];
 build(0, 0, n - 1);
 
 while (q--) 
 {
  cin >> x >> y;
  update(0, 0, n - 1, x - 1, y);
  cout<<tree[0].first<<endl;
 
 }
return 0;
}

service lane problem in hacker rank