мега круте дерево відрізків

#include <vector>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1e5;

int n, a[N];
int t[2 * N]; // 1. 2*n памяти

void build() { // O(n)
  for (int i = 0; i < n; i++)
    t[n + i] = a[i];
  for (int i = n - 1; i > 0; i--)
    t[i] = t[2 * i] + t[2 * i + 1];
}

// [l..r] 0..n-1
// k --> (2k, 2k+1)
int get( int l, int r, int x, int y ) { // 2,3. O(log(r - l)), маленькая константа
  int sum = 0;
  for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
    if   (l & 1)  sum += t[l++];
    if (!(r & 1)) sum += t[r--];
  }
  return sum;
}

// x >>= 5    x /= 32
// x <<= 5    x *= 32
void change( int i, int x ) {
  i += n, t[i] = x;
  for (i >>= 1; i >= 1; i >>= 1)
    t[i] = t[2 * i] + t[2 * i + 1];
}