Fenwick Trees (Binary Indexed Trees): lowbit Geometry, Point Updates & Range Updates

1. Two's Complement Geometry & The Responsibility Interval

In a 1-indexed Fenwick Tree $T[1 \dots N]$, let $\text{lowbit}(i) = i \mathrel{\&} (-i)$ denote the largest power of two $2^k$ that divides $i$. Because $-i = \sim i + 1$ in two's complement binary representation, all bits below $2^k$ flip from $0 \to 1$ and carry into position $k$, while all bits above $k$ are inverted and masked out by the bitwise AND.

2. $O(N)$ Linear-Time Construction & $O(\log N)$ Binary Lifting (lowerBound)

Calling add(i, A[i]) $N$ times builds a Fenwick tree in $O(N \log N)$ time. We can instead build it in exact $\Theta(N)$ time by propagating each node $T[i]$ directly to its immediate update parent $j = i + (i \mathrel{\&} -i)$ in a single forward loop:

$$\text{For } i = 1 \dots N: \quad j = i + (i \mathrel{\&} -i); \quad \text{if } j \le N \text{ then } T[j] \mathrel{+}= T[i]$$

Furthermore, if all array elements are non-negative ($A[i] \ge 0$), the prefix sums are monotonically non-decreasing. Instead of binary searching over prefixSum(mid) in $O(\log^2 N)$ time, we can find the smallest index $i$ with $\text{prefixSum}(i) \ge k$ in single-pass $O(\log N)$ time via Binary Lifting: test bit steps $p = 2^{\lfloor \log_2 N \rfloor}, \dots, 2, 1$; if $T[\text{idx} + p] < k$, advance $\text{idx} \mathrel{+}= p$ and subtract $k \mathrel{-}= T[\text{idx}]$ because $T[\text{idx} + p]$ stores the exact sum of the next $p$ elements!

3. Range Add & Range Sum Using Two Dual Fenwick Trees

Let $D[i] = A[i] - A[i-1]$ be the difference array of $A$, so adding $+\Delta$ to $A[l \dots r]$ only requires two point updates: $D[l] \mathrel{+}= \Delta$ and $D[r+1] \mathrel{-}= \Delta$. How do we recover the prefix sum $\sum_{i=1}^{x} A[i]$ from $D$? Using summation by parts:

$$\sum_{i=1}^{x} A[i] = \sum_{i=1}^{x} \sum_{j=1}^{i} D[j] = \sum_{j=1}^{x} D[j] \cdot (x - j + 1) = (x + 1)\sum_{j=1}^{x} D[j] - \sum_{j=1}^{x} j \cdot D[j]$$

By maintaining two Fenwick trees—$B_1$ storing $D[j]$ and $B_2$ storing $j \cdot D[j]$—both rangeAdd(l, r, delta) and rangeSum(l, r) execute in $O(\log N)$ time with only $2N$ words of memory!

4. Production Implementation: Fenwick Tree with $O(N)$ Build, Binary Lifting & Range Add/Sum

class FenwickTree {
  /**
   * O(N) linear-time construction from 0-indexed input array
   */
  constructor(arrOrSize) {
    if (typeof arrOrSize === "number") {
      this.n = arrOrSize;
      this.tree = new Float64Array(this.n + 1);
    } else {
      this.n = arrOrSize.length;
      this.tree = new Float64Array(this.n + 1);
      for (let i = 1; i <= this.n; i++) {
        this.tree[i] += arrOrSize[i - 1];
        const parent = i + (i & -i);
        if (parent <= this.n) this.tree[parent] += this.tree[i];
      }
    }
  }

  // Point update: A[idx] += delta (1-indexed: 1 <= idx <= n)
  add(idx, delta) {
    for (let i = idx; i <= this.n; i += i & -i) {
      this.tree[i] += delta;
    }
  }

  // Prefix sum: A[1] + ... + A[idx]
  prefixSum(idx) {
    let sum = 0;
    for (let i = idx; i > 0; i -= i & -i) {
      sum += this.tree[i];
    }
    return sum;
  }

  rangeSum(l, r) {
    return this.prefixSum(r) - this.prefixSum(l - 1);
  }

  /**
   * O(log N) Binary Lifting on Fenwick Tree (requires A[i] >= 0):
   * Returns smallest 1-based index idx such that prefixSum(idx) >= targetSum
   */
  lowerBound(targetSum) {
    let idx = 0;
    let bitMask = 1 << (31 - Math.clz32(this.n));
    for (; bitMask > 0; bitMask >>= 1) {
      const next = idx + bitMask;
      if (next <= this.n && this.tree[next] < targetSum) {
        idx = next;
        targetSum -= this.tree[next];
      }
    }
    return idx + 1;
  }
}

/**
 * Dual Fenwick Tree supporting both Range Add and Range Sum in O(log N)
 */
class RangeFenwickTree {
  constructor(n) {
    this.n = n;
    this.b1 = new FenwickTree(n); // stores D[i]
    this.b2 = new FenwickTree(n); // stores i * D[i]
  }

  rangeAdd(l, r, delta) {
    this.b1.add(l, delta);
    this.b1.add(r + 1, -delta);
    this.b2.add(l, delta * l);
    this.b2.add(r + 1, -delta * (r + 1));
  }

  prefixSum(x) {
    return (x + 1) * this.b1.prefixSum(x) - this.b2.prefixSum(x);
  }

  rangeSum(l, r) {
    return this.prefixSum(r) - this.prefixSum(l - 1);
  }
}

5. Complexity Matrix