Bo2SS

[What problems are mainly focused on in learning data structures]

Course Content#

Prerequisite Knowledge#

• What problem is being solved? Modification and query of intervals [For Multiplicative Functions——Wiki]
• Problem Background
  • 
  • Point modification, interval query (basic version)
    • Modify(ind, val): Change 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)
  • Point modification, point query (no need for segment tree, an array is sufficient)
  • Interval modification, point query (actually a special case of the advanced version)

Basic Version of Segment Tree#

• A tree composed of intervals → A tree composed of sums of intervals [Segment Tree]
  • 
  • 👇
  • 
  • 【Construction Process】 Uses a divide-and-conquer approach, dividing the total interval into left and right parts, continuing until only one node remains in the interval
  • 【Property to Maintain】 The node counts the sum of an interval
    • Leaf nodes represent the value of a single position in the original sequence
  • [PS] Review: The nodes of the tree represent a set, and the edges represent relationships
• Point Modification
  • Recursively find the node to be modified, modify it, and then
  • Backtrack, modifying the sum of each ancestor node on the path [from root node to leaf node]
• Interval Query
  • A point may represent the sum of an interval, making queries faster
    • If using an array directly, values need to be queried one by one
    • If using a prefix sum array, point modifications are very time-consuming
• ⭐The segment tree is actually a high-level data structure used to maintain one-dimensional sequences
  • Time Complexity [related to tree height]
    • Point Modification: O(logN)
    • Interval Query: O(logN)
    • N represents the length of the one-dimensional sequence
• ❓ Problem Thinking
  • If using a complete binary tree storage method, how many node spaces are needed for a segment tree with N points? 【4N】
    • First consider using a regular binary tree [a segment tree must be a full binary tree] for storage, refer to the above diagram
    • The number of leaf nodes is N, then the number of nodes with degree 2 is N - 1 [Property of Binary Trees: There is one more node with degree 0 than with degree 2], so the total number of nodes is 2N - 1
    • If using a complete binary tree storage method, then it is necessary to reserve space for 2 times the number of leaf nodes, 2N [Property of Complete Binary Trees: The index of two child nodes is related to the parent node i as 2i and 2i + 1]
    • Therefore, at most 4N node spaces are needed
  • How to perform interval modifications? [Modify every 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 pants to fart"
    • Directly modifying the original interval: O(m), which is better than using a segment tree
    • Please see the advanced version: O(logN)
• [PS] Only applicable for point modifications and interval queries 【Basic Version】
  • When facing interval modifications, the efficiency of the basic version of the segment tree is not as good as directly modifying the one-dimensional sequence

Advanced Version of Segment Tree#

Interval Modification [⭐]#

• Modify Operation
  • 
  • ⭐Lazy Marking: Do not immediately pass values to its child nodes, only pass them down when encountering a node query [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 hold it until the emperor personally inspects before distributing the food
• Query Operation
  • 
  • Triggers lazy marking to pass down values
• Time Complexity [same as interval query operation]: O(logN)

Keywords#

• Complete Binary Tree [Storage Structure]
• Interval [The maintenance range of each node]
• Upward Update [Backtracking Process]
• Downward Mark [Lazy Mark]
• ⭐Mnemonic⭐ Downward marking occurs before recursion, upward updating occurs after recursion
  • Marking down occurs before recursion, and upward updating occurs after recursion with modification operations

In-Class Exercises#

HZOJ-222: Segment Tree Template (One)#

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

• Thought Process
  • The maximum value of the interval where the parent node is located can be obtained from the child nodes
  • 【Application Scenarios of Segment Trees】 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 turn off synchronization, otherwise it will time out
  • When querying the maximum value, always maintain the modified query interval boundaries while narrowing the query range, otherwise there may be a possibility of expanding the query range
• ② Optimized Version [without l, r]
  • 
  • 
  • 
  • Space optimization can be done: nodes do not store l, r information
    • Does not affect the tree construction process
    • ⭐Modification and query operations additionally add [the range of the interval maintained by the current node]

HZOJ-223: Segment Tree Template (Two)#

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

• Thought Process
  • Add lazy marking
  • Note the output prompt: The answer is within the long long range
• Code
  • 
  • 
  • 
  • Be sure to distinguish between [the interval range maintained by the node l ~ r] and [the query interval x ~ y]
  • [PS] Learn to use flags to achieve the effect of commenting and debugging code; the data range is long long
  • ⭐⭐⭐ As long as traversal occurs, marking down is necessary, even during interval modifications
    • If marking down is not done while traversing nodes during interval modifications, upward updating may cause problems
    • You can try testing the outputs of the following inputs under two methods
      • ❗ Continuous interval modifications, the second modification layer is deeper, and upward updating may overlook lazy marking because it only considers the sum of the subtree during upward updating, assuming it has no lazy marking
      • Marking down during traversal is simpler and easier to understand

5 5
1 2 3 4 5
1 1 3 2
1 1 2 2
2 1 3

• The results are as follows:
  • 
  • modify(1, 3, 2) : 1, 1, 5, 15, representing adding 2 to the interval [1, 3], at this time at node 1 [root node], the maintained interval is [1, 5], and the sum is 15
  • Drawing a tree diagram can deepen understanding

Points to Consider#

• Think carefully about the process of marking down and updating upward!

Tips#

• Pay attention to the mnemonic, the captain summarizes it very well!
• More exercises can be found in: 《Interview and Written Algorithm》——6 Tree Array, Segment Tree Exercises