Add chapter Segment Tree Beats

[chihhsi]

Introduction to Segment Tree Beats

• Construct tree node (sum, max1, max2, maxc, min1, min2, minc, lazy tag)
• Construct tree (build)
• Range modification
  • update_add / push_add
  • update_max / push_max
  • update_min / push_min
  • push_down
• Merge functions
• Range query

[chihhsi]

Basic Segment Tree Beats Problems

• RMQ
• For all i in [l, r], change $A_i$ to x
• For all i in [l, r], change $A_i$ to $A_i$+x
• For all i in [l, r], change $A_i$ to max($A_i$-x, 0)
• Codeforces 438D The Child and Sequence

[chihhsi]

Advanced Segment Tree Beats Problems

• Codeforces 1290E Cartesian Tree : For each k in the range [1, n], construct a Cartesian tree using the k smallest values, and find the sum of sizes of all the subtrees in the tree.
• Codeforces 1572F Stations : The i-th city can broadcast to j-th if for all k in [i, j], max{ $h_k$ } < $h_i$
• Given n operations, each providing (l, r, h), place a rectangle with height h on the x-axis between l and r. Find the total perimeter of the resulting shape after each operation.

[chihhsi]

Reference

• https://codeforces.com/blog/entry/57319
• https://usaco.guide/adv/segtree-beats?lang=cpp
• https://www.cnblogs.com/Neal-lee/p/15695984.html
• https://mzhang2021.github.io/cp-blog/historic-segtree

[harry900831]

@chihhsi Missing references