const int N = (int)1e6;

int n, a[N]; // 0..n-1

// a[i] = sum от i & (i+1) до i

// high     low
// 000111001111 = i 
// 000111010000 = i+1
// 000111000000 = i & (i+1)
// 000110111111 = (i & (i+1)) - 1

// high     low
// 000111001111 = i 
// 000111010000 = i+1
// 000111011111 = i | (i+1) = j   i in j & (j+1) .. j

int change( int i, int x )
{
  for (; i < n; i |= i + 1) // logn
    a[i] += x;
}

int get( int i ) // [0..i)
{
  int sum = 0;
  for (; i >= 0; i &= i + 1, i--) // log i
    sum += a[i]; // i & (i+1) .. i
  return sum;
}

int sum( int l, int r )
{
  return get(r) - get(l - 1);
}