Range Sum Query - Mutable

How it works

A Binary Indexed Tree (or Fenwick Tree) uses a clever encoding where each index stores a partial sum based on the binary representation of its index. The key insight is that index & -index gives the lowest set bit, which determines how many elements are summed at each position. This allows both updates and prefix sum queries in logarithmic time with minimal overhead.

Steps

1. Initialize the BIT with size n + 1 (1-indexed).
2. Build by calling update for each element.
3. For update(index, val):
   • Compute diff = val - nums[index].
   • Update nums[index] = val.
   • Walk up the tree, adding diff to each relevant position using index += index & -index.
4. For prefixSum(index):
   • Accumulate sums while walking down using index -= index & -index.
5. For sumRange(left, right):
   • Return prefixSum(right + 1) - prefixSum(left).

Complexity

• Time complexity:
  • O(n) for initializing the input array.
  • O(log n) for each update() function call.
  • O(log n) for each sumRange() function call.
• Space complexity: O(n)

Things to watch for

Confusing Update Value with Delta

When updating a position, some implementations expect the new value while others expect the change (delta) from the old value. In a Fenwick tree, you typically need to compute diff = newValue - oldValue and propagate this difference. Passing the new value directly without computing the delta corrupts the tree, causing all subsequent queries to return incorrect results.

Wrong Index Manipulation in Fenwick Tree

Fenwick trees use 1-based indexing internally because the operation index & -index gives 0 for index 0, causing an infinite loop. Forgetting to convert between 0-based problem indices and 1-based tree indices leads to skipped elements or out-of-bounds access. Always add 1 when accessing the tree and remember the tree array needs size n + 1.

Incorrect Segment Tree Range Boundaries

In segment tree queries, the condition for checking if the current segment is completely outside the query range must be start > right || end < left, not using >= or <=. Similarly, checking if the segment is completely inside should be start >= left && end <= right. Mixing up these conditions causes partial overlaps to be incorrectly handled, returning wrong sums or missing contributions.

from typing import List

class BIT:
    def __init__(self, nums):
        self.n = len(nums) + 1
        self.nums = [0] * self.n
        self.tree = [0] * self.n
        for i in range(self.n - 1):
            self.update(i, nums[i])

    def update(self, index, val):
        index += 1
        diff = val - self.nums[index]
        self.nums[index] = val
        while index < self.n:
            self.tree[index] += diff
            index += index & -index

    def prefix_sum(self, index):
        total_sum = 0
        while index > 0:
            total_sum += self.tree[index]
            index -= index & -index
        return total_sum

    def query(self, left, right):
        return self.prefix_sum(right + 1) - self.prefix_sum(left)


class NumArray:
    def __init__(self, nums: List[int]):
        self.bit = BIT(nums)

    def update(self, index: int, val: int) -> None:
        self.bit.update(index, val)

    def sumRange(self, left: int, right: int) -> int:
        return self.bit.query(left, right)

class BIT {
    vector<int> nums;
    vector<int> tree;
    int n;

public:
    BIT(vector<int>& nums) {
        n = nums.size() + 1;
        this->nums.resize(n);
        tree.resize(n, 0);
        for (int i = 0; i < nums.size(); i++) {
            update(i, nums[i]);
        }
    }

    void update(int index, int val) {
        index++;
        int diff = val - nums[index];
        nums[index] = val;
        while (index < n) {
            tree[index] += diff;
            index += index & -index;
        }
    }

    int prefixSum(int index) {
        int totalSum = 0;
        while (index > 0) {
            totalSum += tree[index];
            index -= index & -index;
        }
        return totalSum;
    }

    int query(int left, int right) {
        return prefixSum(right + 1) - prefixSum(left);
    }
};

class NumArray {
    BIT bit;

public:
    NumArray(vector<int>& nums) : bit(nums) {}

    void update(int index, int val) {
        bit.update(index, val);
    }

    int sumRange(int left, int right) {
        return bit.query(left, right);
    }
};