pst

void dup(int& k){
  ind++;
  sum[ind] = sum[k];
  add[ind] = add[k];
  lc[ind] = lc[k];
  rc[ind] = rc[k];
  k = ind;
}

void U(int p, int val, int& k, int L, int R){
  if(R <= L || p < L || R <= p) return ;
  dup(k);
  if(L + 1 == R){
    sum[k] += val;
    return ;
  }

  int mid = (L + R) / 2;
  U(p, val, lc[k], L, mid);
  U(p, val, rc[k], mid, R);
  sum[k] = sum[lc[k]] + sum[rc[k]];
}

int S(int qL, int qR, int k, int L, int R){
  if(R <= L || qR <= L || R <= qL) return 0;
  if(qL <= L && R <= qR) return sum[k];
  int mid = (L + R) / 2;
  return S(qL, qR, lc[k], L, mid) + S(qL, qR, rc[k], mid, R);
}