Segmenttipuu

Kisakoodarin käsikirjan mukainen toteutus segmenttipuusta:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1 << 17;
ll p[2 * N];

ll summa(int a, int b) {
  a += N; b += N;
  ll s = 0;
  while (a <= b) {
    if (a%2 == 1) s += p[a++];
    if (b%2 == 0) s += p[b--];
    a /= 2; b /= 2;
  }
  return s;
}

void lisaa(int k, ll x) {
  k += N;
  p[k] += x;
  for (k /= 2; k >= 1; k /= 2) {
    p[k] = p[2*k] + p[2*k+1];
  }
}