sqrt_descomposition.cpp

//sqrt descomposition
//complexity:
//  build - O(n)
//  query - O(sqrt n)
//  update - O(1)

const int N = 100005;
int block[350], a[N];
int n, nb;

void build(int n){
  nb = (int) sqrt(n + .0) + 1;
  for(int i = 0; i < n; ++i)
    block[i/nb] += a[i];
}

int query(int l, int r){
  int lb = l/nb, rb = r/nb; 
  int ans = 0;
  if(lb == lr)
    for(int i = l; i <= r; ++i)
      ans += a[i];
  else{
    for(int i = l, i < (lb+1)*nb; ++i)
      ans += a[i];
    for(int i = lb+1; i < rb; ++i)
      ans += b[i];
    for(int i = rb*nb; i <= r; ++i)
      ans += a[i];
  }
  return ans;
}

int update(int x, int v){
  b[x/nb] += v;
  a[x] += v;
}