template<const int N>
struct Fenwick {
  int n, sum[N];

  void build( int n, int *a ) {
    this->n = n;
    copy(a, a + n, sum);
    for (int i = 0; i < n; i++)
      if ((i | (i + 1)) < n)
        sum[i | (i + 1)] += sum[i];
  }

  void add( int y, int d ) {
    for (int x = y; x < n; x |= x + 1)
      sum[x] += d;
  }

  int get( int x ) {
    int r = 0;
    for (; x >= 0; x &= x + 1, x--) 
      r += sum[x]; 
    return r;
  }
  int get( int l, int r ) {
    return get(r) - get(l - 1);
  }
};