segment_tree.cpp

//segment tree
//complexity:
//  merge - O(1)
//  shift - O(1)
//  upd - O(1)
// build - O(n)
// update - O(log n)
//  query - O(log n)

const int maxN = 100002;
int ft[maxN<<2], a[maxN];
int lazy[maxN<<2];
int n;

int merge(int p, int q){
  return min(p, q); 
}

void upd(int nx, int l, int r, int x){
  lazy[nx] += x;
  st[nx] += x;
}

void shift(int nx, int l, int r, int mid){
  upd(2*nx, l, mid, lazy[nx]);
  upd(2*nx+1, mid+1, r, lazy[nx]);
  lazy[nx] = 0;
}

void build(int nx = 1, int l = 0, int r = n-1){
  if(l == r){
    st[nx] = a[r];
    return;
  }
  
  int mid = (l+r)/2;
  build(2*nx  , l   , mid);
  build(2*nx+1, mid+1, r );
  st[nx] = merge(st[2*nx], st[2*nx+1]);
}

void update(int x, int y, int z, int nx = 1, int l = 0, int r = n-1){
  if(y < l or r < x) return;  
  if(x <= l and r <= y){
      upd(nx, l, r, z);
      return;
  }
  
  int mid = (l+r)/2;
  shift(nx, l, r, mid);
  update(x, y, z, 2*nx   , l     , mid);
  update(x, y, z, 2*nx+1 , mid+1 , r  );
  
  st[nx] = merge(st[2*nx], st[2*nx+1]);
}

int query(int x, int y, int nx = 1, int l = 0, int r = n-1){
  if(y < l or r < x) return INT_MAX;
  if(x <= l and r <= y) return st[nx];
  
  int mid = (l+r)/2;
  shift(nx, l, r, mid);
  int L = query(x, y, 2*nx  , l     , mid);
  int R = query(x, y, 2*nx+1, mid+1 , r  );
  
  return merge(L, R);
}