Segment Tree (Range Sum)

The invariant: tree[node] is always the sum of nums[lo..hi] for that node's range.

Why 4n slots: the tree has height ⌈log2 n⌉, so the largest index used is below 2 · 2^⌈log2 n⌉ ≤ 4n. When n is a power of two only 2n − 1 slots are used; the rest stay 0.

How it works

1. build(node, lo, hi): if lo === hi, store nums[lo]. Otherwise build both halves recursively and store their sum (post-order: children first).
2. query(l, r) visits queryRange(node, lo, hi) from the root:
   • no overlap (r < lo or hi < l): return 0,
   • total overlap (l ≤ lo and hi ≤ r): return tree[node] without going deeper,
   • partial overlap: return the sum of both children's answers.
3. update(index, val): walk down toward the leaf for index (left if index ≤ mid, else right), overwrite the leaf, then recompute each ancestor's sum on the way back up.

Walkthrough

Case 0: nums = [2, 1, 5, 3], then query(1, 3), update(2, 4), query(1, 3), query(0, 2).

build (children are filled before their parent):

node  range   sum
 3    [0,0]    2
 4    [1,1]    1
 1    [0,1]    3   = tree[3] + tree[4]
 5    [2,2]    5
 6    [3,3]    3
 2    [2,3]    8   = tree[5] + tree[6]
 0    [0,3]   11   = tree[1] + tree[2]
tree = [11, 3, 8, 2, 1, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0]   (slots 7..15 unused)

query(1, 3)

node 0 [0,3]  partial -> split at mid 1
  node 1 [0,1]  partial -> split at mid 0
    node 3 [0,0]  no overlap        -> 0
    node 4 [1,1]  inside            -> 1
  node 2 [2,3]  inside              -> 8
answer 0 + 1 + 8 = 9

update(2, 4): 2 > mid 1 → node 2 [2,3]; 2 ≤ mid 2 → node 5 [2,2] becomes 4. Back up: node 2 = 4 + 3 = 7, node 0 = 3 + 7 = 10.

tree = [10, 3, 7, 2, 1, 4, 3, 0, ...]

query(1, 3) now returns 1 + 7 = 8; query(0, 2) takes node 1 [0,1] whole (3) and node 5 [2,2] (4) for 7.

Complexity

When to use it

• Strengths: handles any associative operation (sum, min, max, gcd, xor) by changing the combine step; extends to range updates with lazy propagation and to persistent or 2D versions.
• vs. prefix sums: O(1) queries but O(n) updates; best when the array never changes.
• vs. Fenwick tree: a Fenwick tree is shorter, uses n + 1 slots and is faster in practice, but only works for invertible operations like sum (no range min/max).
• vs. sqrt decomposition: simpler, but O(√n) per operation.
• Weaknesses: more code and memory than a Fenwick tree; recursion overhead (an iterative bottom-up version avoids it).

Common pitfalls

• Allocating only 2n slots for the recursive layout: with n not a power of two, indices can exceed 2n (use 4n).
• Mixing the node index with the array index: node addresses tree, while lo, hi and index address nums.
• Wrong overlap tests (r < lo || hi < l is "no overlap"); off-by-one with mid versus mid + 1 for the right child.
• Forgetting to recompute the ancestors after an update, or treating update as "add delta" when the API says "set value".
• Returning the wrong neutral value for no overlap (0 for sum, Infinity for min, -Infinity for max).

What to watch in the visualizer

• this.tree is drawn as a binary heap: the tree view shows each node's sum, the array below it shows the real storage, unused slots included.
• node is the only index into tree, so its chip marks the slot being visited, both in the tree view and in the array row.
• lo, hi and mid are positions in nums, not in tree: during build they appear as chips on nums; in queryRange and updatePoint read them in the locals panel to see which range the current node covers.
• During build, sums appear bottom-up; during update, watch the changed leaf and then its ancestors flash as they are recomputed.
• The call stack shows the recursion: queryRange returns early (no overlap or total overlap) on most branches.

Example

Input:
  ["SegmentTree", "query", "update", "query", "query"]
  [[[2, 1, 5, 3]], [1, 3], [2, 4], [1, 3], [0, 2]]
Output:
  [null, 9, null, 8, 7]

Constraints

• 1 <= nums.length <= 3 * 10^4
• 0 <= index < nums.length, 0 <= l <= r < nums.length
• At most 3 * 10^4 calls to update and query.