Segment Tree
A binary tree whose leaves are the array and whose every parent summarises its two children.
Segment Tree: Build a sum tree
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)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Segment Tree covers these too, in the same run.