Array (3–8 integers, comma-separated)

Query lo

Query hi

Update idx

Update → value

Array53819274

Query[1…5]update arr[] →

current nodecontributes to queryleaf

1 / 47

Speed

Build a sum segment tree over [5, 3, 8, 1, 9, 2, 7, 4] (8 leaves). Node 1 covers the whole array.

Nodes

Query result

—

Contributing nodes

Root sum

—

segment-tree.js

1function build(node, lo, hi) {

2 if (lo === hi)

3 return (tree[node] = arr[lo]);

4 const mid = (lo + hi) >> 1;

5 tree[node] = merge(

6 build(2*node, lo, mid),

7 build(2*node+1, mid+1, hi));

8 return tree[node];

11function query(node, lo, hi, qlo, qhi) {

12 if (qhi < lo || hi < qlo) return NEUTRAL;

13 if (qlo <= lo && hi <= qhi)

14 return tree[node]; // fully covered

15 const mid = (lo + hi) >> 1;

16 return merge(

17 query(2*node, ...), query(2*node+1, ...));

18}

Build → query → update run back to back · Green nodes contributed to the query result

About the Segment Tree algorithm

Range queries and point updates in O(log n) via a binary decomposition of the array. Watch queries split, recurse, and merge.

Category: Data Structures
Difficulty: Hard
Time complexity: O(log n) per op
Space complexity: O(n)