notebook/code/SegmentTree.cpp

// segment tree for minimum
// root is in tree[1], children in tree[2i] and tree[2i+1]
// all ranges in build/updates/queries are 0-based
const int INFI=1000000000;
struct Node {
  int v; int up;
  void update(int x) {
    v += x;
    up += x;
  }
  Node() {
    v = INFI;
    up = 0;
  }
};
Node *tree;
int N;
// read values[0..size-1]
void build(int size, int values[]) {
  N = 1 << ((int)log2(size-1)+1);
  tree = new Node[2*N];
  for(int i = 0; i < size; i++) // leaves
    tree[N+i].v = values[i];
  for(int i = N-1; i > 0; i--) // interns
    tree[i].v = min(tree[2*i].v, tree[2*i+1].v);
}
void push(int v) {
  if(2*v < 2*N) // left subtree
    tree[2*v].update(tree[v].up);
  if(2*v+1 < 2*N) // right subtree
    tree[2*v+1].update(tree[v].up);
  tree[v].up = 0;
}
// v: current vertex with corressponding range [left, right)
// find mimimum in the rangeg [l, r)
int query_aux(int v, int left, int right, int l, int r) {
  push(v);
  if(right <= l || r <= left) // outside
    return INFI;
  if(l <= left && right <= r) // inside
    return tree[v].v;
  int m = (left+right)/2;
  int left_min = query_aux(2*v, left, m, l, r); // left subtree
  int right_min = query_aux(2*v+1, m, right, l, r); // right
  return min(left_min, right_min);
}
int query(int l, int r) {
  return query_aux(1, 0, N, l, r);
}
// update element at index i with value x
void update(int i, int x) {
  i+=N;
  // push path from 1 to i
  int po = N;
  for(int v = 1; v < i;) {
    push(v);
    if(i & po)
	  v = 2*v + 1; // i on right
    else
	  v = 2*v; // left
	po /= 2;
  }
  tree[i].v = x; // update el
  for(i /= 2; i > 0; i /= 2) // update all segments containing i
    tree[i].v = min(tree[2*i].v, tree[2*i+1].v);
}
// v: the current vertex with corressponding range in [left, right)
// add value x for element in range [l, r)
void update_range_aux(int v, int left, int right, int l, int r, int x) {
  push(v);
  if(right <= l || r <= left)
    return;
  if(l <= left && right <= r) {
    tree[v].update(x);
    return;
  }
  int m = (left+right)/2;
  update_range_aux(2*v, left, m, l, r, x);
  update_range_aux(2*v+1, m, right, l, r, x);
  tree[v].v = min(tree[2*v].v, tree[2*v+1].v);
}
// update [l,r)
void update_range(int l, int r, int x) {
  update_range_aux(1, 0, N, l, r, x);
}