AlgoScope

Segment Tree Query and Update

A query takes whole nodes inside the range and splits only the ones on its edge.

Range queries, algorithm, advanced
Node 1 covers indices 0 to 7. Partly inside, so both children are checked.58316781364106202108current

Segment Tree: Sum of indices 2 to 5

Decision, step 2 of 9

Node 1 covers indices 0 to 7, holding 36. That straddles the edge, so split into both children.

How segment tree works

Cost

Best
O(log n)
Average
O(log n)
Worst
O(log n)
Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

Segment Tree covers these too, in the same run.