Algorithm in LeetCode —— Segment Tree

Tips for Segment Tree:

• The classic array-based implementation of a segment tree. The pushUp logic for merging two nodes is abstracted out, so arbitrary operations can be implemented (common operations include addition, taking max, min, etc.). Problems 218, 303, 307, and 699.
• The classic implementation of a counting segment tree. Problems 315, 327, and 493.
• The tree-based implementation of a segment tree. Problems 715 and 732.
• Lazy range updates. Problems 218 and 699.
• Discretization. Pay attention to one special case in discretization: suppose the three intervals are [1,10], [1,4], and [6,10]. After discretization, x[1]=1,x[2]=4,x[3]=6,x[4]=10. The first interval becomes [1,4], the second becomes [1,2], and the third becomes [3,4]. As a result, interval one = interval two + interval three, which does not match the model before discretization. Before discretization, it is obvious that interval one > interval two + interval three. The correct approach is to add a number between values whose difference is greater than 1. For example, add 5 between 4 and 6 in 1 4 6 10 above, yielding x[1]=1,x[2]=4,x[3]=5,x[4]=6,x[5]=10. After this processing, interval one is 1-5, interval two is 1-2, and interval three is 4-5.
• Build segment trees flexibly. A segment tree node can store multiple pieces of information, and the pushUp operation that merges two nodes can also take many forms. Problems 850 and 1157.

Segment tree problem types, from easy to hard:

1. Point updates:
   HDU 1166 Enemy Troops update: point increment/decrement query: range sum
   HDU 1754 I Hate It update: point replacement query: range extremum
   HDU 1394 Minimum Inversion Number update: point increment/decrement query: range sum
   HDU 2795 Billboard query: find the position of the maximum value in a range (the update operation is performed directly inside query)
2. Range updates:
   HDU 1698 Just a Hook update: range replacement (because only the full range is queried once, you can directly output the information of node 1)
   POJ 3468 A Simple Problem with Integers update: range increment/decrement query: range sum
   POJ 2528 Mayor’s posters discretization + update: range replacement query: simple hashing
   POJ 3225 Help with Intervals update: range replacement, interval XOR query: simple hashing
3. Range merging (these problems ask for the longest contiguous interval within a range that satisfies certain conditions, so during PushUp, the intervals of the left and right children need to be merged):
   POJ 3667 Hotel update: range replacement query: ask for the leftmost endpoint that satisfies the condition
4. Sweep line (these problems require sorting a set of operations, then sweeping from left to right with a sweep line. The most typical examples are union area of rectangles, union perimeter, and similar problems):
   HDU 1542 Atlantis update: range increment/decrement query: directly take the value of the root node
   HDU 1828 Picture update: range increment/decrement query: directly take the value of the root node