The O(n) Club: Range Sum Query – Mutable (Or Why Prefix Sums Need Therapy)

The O(n) Club: Range Sum Query – Mutable (Or Why Prefix Sums Need Therapy)

⚡ TL;DR

If you want fast range sums and in-place updates, basic prefix sums will break your heart. Grab a segment tree or BIT and do this instead:

// The naive way: slow and sad (O(n))
public int sumRange(int left, int right) {
    int sum = 0;
    for (int i = left; i <= right; i++) sum += nums[i];
    return sum;
}

🧠 How Devs Usually Mess This Up

So you try prefix sums (it worked last time!). Then the array mutates and you realize every update means recalculating everything after the change. Not fun. Instead of O(log n), you’re stuck in O(n) purgatory. And if you brute-force the sumRange, it’s like counting coins on the ground instead of using a cash register. Please, respect your wrists’ future carpal tunnel.

🔍 What’s Actually Going On

Think of this like a restaurant kitchen: you don’t want the chef to chop all the veggies every time someone asks for a salad. You want prepared bins (segment tree nodes/BIT) with pre-aggregated ingredients. Each update changes only the bins that matter. Each query scoops ingredients from just the right buckets. That’s logarithmic efficiency for both cooks and code.

🛠️ PseudoCode

• Build a segment tree (or BIT) over your array.

  // Node struct
  class Node {
    int left, right, sum;
    Node leftChild, rightChild;
  }

  Each node keeps the sum for its range. Parents = sum of children.

• To update an element: update the leaf & climb, fixing parent sums on the path.
• To sumRange(l, r): recursively collect sums from nodes covering l .. r (avoid overlap, be greedy).
• Both operations are O(log n): segment trees make sure you never do more.

💻 The Code

// Fast Segment Tree for range sum + updates
class NumArray {
    private int[] tree, nums;
    private int n;
     public NumArray(int[] nums) {
        this.n = nums.length;
        this.nums = nums.clone();
        this.tree = new int[n * 2];
        build();
    }
     private void build() {
        for (int i = 0; i < n; ++i)
            tree[n + i] = nums[i];
        for (int i = n - 1; i > 0; --i)
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
    }
     public void update(int i, int val) {
        int pos = i + n;
        tree[pos] = val;
        while (pos > 1) {
            pos /= 2;
            tree[pos] = tree[2 * pos] + tree[2 * pos + 1];
        }
    }
     public int sumRange(int left, int right) {
        int l = left + n, r = right + n, sum = 0;
        while (l <= r) {
            if ((l & 1) == 1) sum += tree[l++];
            if ((r & 1) == 0) sum += tree[r--];
            l /= 2; r /= 2;
        }
        return sum;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Prefix sum arrays only work if nothing ever changes (so, never in production).
• The usual off-by-one bug festival: segment trees use 0 or 1-based indexing, pick one and stick to it like a stubborn mutex.
• Memory: Segment trees double array size; BITs are lighter.
• Both update & query are O(log n), so don’t over-promise “instant” analytics if n is gigantic.

🧠 Interviewer Brain-Tattoo

“Prefix sums are great until you need to change something. Segment trees: for dynamic arrays and devs who hate being O(n) slow.”