Segment Tree

A segment tree is a binary tree built over an array in which each node stores an aggregate — here, the sum — of a contiguous slice of that array, so that both range-sum queries and single-element updates run in O(log n) time. That combination is the point: a plain array can update a slot in O(1) but needs O(n) to add up a range, and a prefix-sum array flips the trade (O(1) range sums, but O(n) to rebuild after any update). A segment tree gets both operations to O(log n), which is what you want when reads and writes are interleaved. Your segmentTree(arr) factory builds the tree over a copy of arr and returns an object with two methods, query and update.

Signature

function segmentTree(arr: number[]): {
  query(l: number, r: number): number;   // sum of arr[l..r], inclusive
  update(i: number, value: number): void; // set arr[i] = value, fix the tree
};

Examples

const st = segmentTree([1, 3, 5, 7, 9, 11]);
st.query(0, 5); // 36  — the whole array
st.query(1, 3); // 15  — 3 + 5 + 7
st.query(2, 2); // 5   — a single element

const st = segmentTree([1, 3, 5, 7, 9, 11]);
st.update(2, 10); // index 2 changes from 5 to 10
st.query(0, 5);   // 41  — the total went up by 5
st.query(1, 3);   // 20  — 3 + 10 + 7

Notes

• Inclusive range — query(l, r) sums every element from index l to index r, including both ends. query(2, 2) is a single element.
• Zero-indexed — the first element is index 0, the last is index n - 1.
• Sum aggregate — this tree combines slices with addition. The same shape supports min, max, or gcd by swapping the combine step (see the solution's Going further).
• Both operations are O(log n) — a linear scan for query or a full rebuild for update defeats the purpose.
• Valid inputs only — assume arr is non-empty and every query satisfies 0 <= l <= r < arr.length. You do not need to guard against out-of-range indices.