i --> i / 2
i --> 2 * i, 2 * i + 1


// 0 <= l, r < n
get(l, r)
{
  int sum = 0;
  l += n, r += n;
  while (l <= r)
  {
    if (l % 2 == 1)
      sum += t[l++];
    if (r % 2 == 0)
      sum += t[r--];
    l /= 2, r /= 2;
  }
  return sum; 
}

const int N = (int)1.1e6

int n, t[4 * N];

int get(l, r)
{
  int sum = 0;
  for (l += n, r += n; l <= r; l /= 2, r /= 2)
  {
    if (l % 2 == 1) sum += t[l++];
    if (r % 2 == 0) sum += t[r--];
  }
  return sum; 
}

void build( int k, int *a )
{
  int n = 1; // k --> n = 2^t
  while (n < k)
    n <<= 1;
  forn(i, k)
    t[i + n] = a[i]; // n - k
  for (int i = n - 1; i >= 1; i--)
    t[i] = t[2 * i] + t[2 * i + 1];  
}