Fenwick Tree (BIT) — Range Sums in Half the Code

void update(int i, int delta) {
  while (i <= n) {
    bit[i] += delta;
    i += i & -i;  // add lowest set bit
  }
}

long query(int i) {
  long sum = 0;
  while (i > 0) {
    sum += bit[i];
    i -= i & -i;  // strip lowest set bit
  }
  return sum;
}