Segment Tree

[What problem does learning data structures mainly focus on solving?]

Course Content#

Prerequisite Knowledge#

What problem does it solve? Interval modification and query [for multiplicative function - Wiki]
Problem background
- Single point modification, interval query (basic version)
  - Modify(ind, val): Modify the value at position ind to val
  - Query(start, end): Query the sum of values from start to end
- Interval modification, interval query (advanced version)
- Single point modification, single point query (no need for segment tree, array is sufficient)
- Interval modification, single point query (actually a special case of the advanced version)

Basic Version of Segment Tree#

Tree composed of intervals → Tree composed of sum values of intervals [Segment Tree]
- 👇
- 【Construction process】Using the divide and conquer approach, divide the total interval into left and right parts until there is only one node left in the interval
- 【Property to maintain】The node represents the sum value of an interval
  - Leaf nodes represent the value at a single position in the original sequence
- [PS] Review: Nodes represent sets, edges represent relationships
Single point modification
- Recursively find the node to be modified, modify it, and then
- Backtrack and modify the sum value of each ancestor node on the path [from the root node to the leaf node]
Interval query
- A point may represent the sum value of an interval, which makes the query faster
  - If using an array directly, each value needs to be queried one by one
  - If using a prefix sum array, single point modification is very time-consuming
⭐Segment tree is actually an advanced data structure for maintaining one-dimensional sequences
- Time complexity [related to the height of the tree]
  - Single point modification: O(logN)
  - Interval query: O(logN)
  - N represents the length of the one-dimensional sequence
❓ Problem thinking
- If the complete binary tree storage method is used, how many node spaces are needed for a segment tree with N nodes? [4N]
  - First consider using a normal binary tree [segment tree is always a full binary tree] for storage, refer to the above figure
  - The number of leaf nodes is N, so the number of nodes with a degree of 2 is N - 1 [Property of binary tree: The number of nodes with a degree of 0 is one more than the number of nodes with a degree of 2], so the number of nodes is 2N - 1
  - If the storage method of a complete binary tree is used, at most 2 times the number of leaf nodes of node space is needed, 2N [Property of complete binary tree: The relationship between the index of two child nodes and the parent node i is 2i and 2i + 1]
  - So a maximum of 4N node spaces are needed
- How to do interval modification? [Modify each value in an interval of size m]
  - Based on the basic operations of the segment tree: O(m * logN), which is equivalent to taking off your pants and farting
  - Modifying directly on the original interval: O(m), which is better than using a segment tree itself
  - Please refer to the advanced version: O(logN)
[PS] Only applicable to single point modification, interval query [basic version]
- When facing interval modification, the efficiency of the basic version of the segment tree is not as good as modifying directly on the one-dimensional sequence

Advanced Version of Segment Tree#

Interval Modification [⭐]#

Modify operation
- ⭐Lazy tag: Do not immediately propagate values to its child nodes, only propagate when encountering node queries [Modification operation/Query operation traversal]
- Analogy to "lazy governance": The emperor [root node] distributes food to the people [leaf nodes], first giving it to the superiors [child nodes], who will keep it until the emperor inspects it and then distribute the food
Query operation
- Trigger the propagation of lazy tags
Time complexity [same as interval query operation]: O(logN)

Keywords#

Complete binary tree [storage structure]
Interval [maintenance range of each node]
Upward update [backtracking process]
Downward propagation [lazy tag]
⭐Mnemonic⭐ Downward propagation occurs before recursion, upward update occurs after recursion with modification operation
- The downward propagation occurs before recursion, and the upward update occurs after the recursion with the modification operation
Maintain the format [same as the original]

In-class Exercises#

HZOJ-222: Segment Tree Template (1)#

Sample Input

6 5
6 9 4 3 2 1
2 2 5
1 2 3
2 1 6
1 5 12
2 1 6

Sample Output

9
6
12

Idea
- The maximum value of the parent node's interval can be obtained from the child nodes
- 【Application scenario of segment tree】The relevant information of the parent node can be obtained from the child nodes
Code
① Easy-to-understand version [with l, r]
- Use scanf/printf to read data or disable synchronization, otherwise it will exceed the time limit
- When performing a query for the maximum value, always keep modifying the query interval boundaries to narrow the query range, otherwise there may be a possibility of expanding the query interval
② Optimized version [without l, r]
- Space optimization can be done: the nodes do not store l, r information
  - It does not affect the tree construction process
  - ⭐Additional information about the range of intervals maintained by the modification and query operations

HZOJ-223: Segment Tree Template (2)#

Sample Input

6 5
6 9 4 3 2 1
2 2 5
1 2 3 5
2 1 6
1 5 12 3
2 1 6

Sample Output

18
35
41

Idea
- Add lazy tags
- Pay attention to the output prompt: the answer is within the range of long long
Code
- Distinguish between the range l ~ r maintained by the node and the query range x ~ y
- [PS] Learn to use the flag to comment and debug the code; the data range is long long
- ⭐⭐⭐Whenever traversal is needed, downward propagation is required, even in interval modification
  - If the lazy tag is not propagated when traversing the nodes in the interval modification, the upward update may cause problems
  - You can try to test the two methods and the following input and output
    - ❗ Continuous interval modification, the second modification is deeper, and the upward update may not consider the lazy tag, because the upward update and value operation only look at the sum value of the subtree by default, assuming that there is no lazy tag
    - It is simpler and easier to understand to propagate the tag when traversing

The result is as follows:
- modify(1, 3, 2): 1, 1, 5, 15, which means adding 2 to the [1, 3] interval, at this time in node 1 [root node], maintaining the interval [1, 5], and the sum is 15
- Draw the tree diagram yourself to deepen your understanding

Points to Consider#

Think carefully about the process of downward propagation and upward update!

Tips#

Pay attention to the mnemonic, Captain summarized it wonderfully!
For more exercises, you can refer to: "Interview and Written Test Algorithms" - 6 Binary Indexed Tree, Segment Tree Exercises