Segment Tree
Last updated
Was this helpful?
Last updated
Was this helpful?
线段树的经典数组实现写法。将合并两个节点 pushUp 逻辑抽象出来了，可以实现任意操作(常见的操作有：加法，取 max，min 等等)。第 218 题，第 303 题，第 307 题，第 699 题。
计数线段树的经典写法。第 315 题，第 327 题，第 493 题。
线段树的树的实现写法。第 715 题，第 732 题。
区间懒惰更新。第 218 题，第 699 题。
离散化。离散化需要注意一个特殊情况：假如三个区间为 [1,10] [1,4] [6,10]，离散化后 x[1]=1,x[2]=4,x[3]=6,x[4]=10。第一个区间为 [1,4]，第二个区间为 [1,2]，第三个区间为 [3,4]，这样一来，区间一 = 区间二 + 区间三，这和离散前的模型不符，离散前，很明显，区间一 > 区间二 + 区间三。正确的做法是：在相差大于 1 的数间加一个数，例如在上面 1 4 6 10 中间加 5，即可 x[1]=1,x[2]=4,x[3]=5,x[4]=6,x[5]=10。这样处理之后，区间一是 1-5 ，区间二是 1-2 ，区间三是 4-5 。
灵活构建线段树。线段树节点可以存储多条信息，合并两个节点的 pushUp 操作也可以是多样的。第 850 题，第 1157 题。
线段树从简单到困难:
单点更新:
update:单点增减 query:区间求和
update:单点替换 query:区间最值
update:单点增减 query:区间求和
query:区间求最大值的位子(直接把update的操作在query里做了)
区间更新:
update:成段替换 (由于只query一次总区间,所以可以直接输出 1 结点的信息)
update:成段增减 query:区间求和
离散化 + update:成段替换 query:简单hash
update:成段替换,区间异或 query:简单hash
区间合并(这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并):
update:区间替换 query:询问满足条件的最左端点
扫描线(这类题目需要将一些操作排序,然后从左到右用一根扫描线扫过去最典型的就是矩形面积并,周长并等题):
update:区间增减 query:直接取根节点的值
update:区间增减 query:直接取根节点的值
No.
Title
Solution
Difficulty
TimeComplexity
SpaceComplexity
Favorite
Acceptance
0218
The Skyline Problem
Hard
O(n log n)
O(n)
❤️
36.2%
0307
Range Sum Query - Mutable
Medium
O(1)
O(n)
36.6%
0315
Count of Smaller Numbers After Self
Hard
O(n log n)
O(n)
42.6%
0327
Count of Range Sum
Hard
O(n log n)
O(n)
❤️
35.9%
0493
Reverse Pairs
Hard
O(n log n)
O(n)
26.6%
0699
Falling Squares
Hard
O(n log n)
O(n)
❤️
42.4%
0715
Range Module
Hard
O(log n)
O(n)
❤️
40.1%
0732
My Calendar III
Hard
O(log n)
O(n)
❤️
61.5%
0850
Rectangle Area II
Hard
O(n log n)
O(n)
❤️
48.3%
1157
Online Majority Element In Subarray
Hard
O(log n)
O(n)
❤️
39.6%
1649
Create Sorted Array through Instructions
Hard
36.2%
------------
-------------------------------------------------------
-------
----------------
---------------
-------------
-------------
-------------