Segment trees for range queries and updates · 1 of 3 Advanced
Point updates and range queries
Answer range minimums and sums while single values change, with a tree whose every node stores the answer for its own range.
Books1
Links4
- Point Update Range Sum Recursive and loop implementations for Dynamic Range Minimum Queries and Dynamic Range Sum Queries, with a practice list. usaco.guide (opens in a new tab)
- Segment Tree The same recursive tree in more detail, followed by the variations that the later pages of this lesson teach. cp-algorithms.com (opens in a new tab)
- 线段树基础 The recursive tree with a diagram of each node’s interval, then lazy tags and dynamic nodes for very large index ranges. oi-wiki.org (opens in a new tab)
- Open Data Structures, section 10.1: BinaryHeap: An Implicit Binary Tree The same array layout for a heap, numbered from 0. Parts of this page adapt this section's text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code. opendatastructures.org (opens in a new tab)