AlgoScope

Segment Tree

A binary tree whose leaves are the array and whose every parent summarises its two children.

Data structures, data structure, advanced
Node 1 becomes 36.58316781364106202108current

Segment Tree: Build a sum tree

Step, step 8 of 9

Node 1 covers indices 0 to 7. Its children hold 16 and 20, so it holds 36.

Cost

Build
O(n)
Query
O(log n)
Update
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.