Discover more content...

Discover more content...

Enter some keywords in the search box above, we will do our best to offer you relevant results.

Results

We're sorry!

Sorry about that!

We couldn't find any results for your search. Please try again with another keywords.

LeetCode 分类刷题 —— Segment Tree

Segment Tree 的 Tips:

  • 线段数的经典数组实现写法。将合并两个节点 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 题。

线段树题型从简单到困难:

  1. 单点更新:
    HDU 1166 敌兵布阵 update:单点增减 query:区间求和
    HDU 1754 I Hate It update:单点替换 query:区间最值
    HDU 1394 Minimum Inversion Number update:单点增减 query:区间求和
    HDU 2795 Billboard query:区间求最大值的位子(直接把update的操作在query里做了)
  2. 区间更新:
    HDU 1698 Just a Hook update:成段替换 (由于只query一次总区间,所以可以直接输出 1 结点的信息)
    POJ 3468 A Simple Problem with Integers update:成段增减 query:区间求和
    POJ 2528 Mayor’s posters 离散化 + update:成段替换 query:简单hash
    POJ 3225 Help with Intervals update:成段替换,区间异或 query:简单hash
  3. 区间合并(这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并):
    POJ 3667 Hotel update:区间替换 query:询问满足条件的最左端点
  4. 扫描线(这类题目需要将一些操作排序,然后从左到右用一根扫描线扫过去最典型的就是矩形面积并,周长并等题):
    HDU 1542 Atlantis update:区间增减 query:直接取根节点的值
    HDU 1828 Picture update:区间增减 query:直接取根节点的值
Title Solution Difficulty Time Space 收藏
218. The Skyline Problem Go Hard O(n log n) O(n) ❤️
307. Range Sum Query - Mutable Go Hard O(1) O(n)
315. Count of Smaller Numbers After Self Go Hard O(n log n) O(n)
327. Count of Range Sum Go Hard O(n log n) O(n) ❤️
493. Reverse Pairs Go Hard O(n log n) O(n)
699. Falling Squares Go Hard O(n log n) O(n) ❤️
715. Range Module Go Hard O(log n) O(n) ❤️
732. My Calendar III Go Hard O(log n) O(n) ❤️
850. Rectangle Area II Go Hard O(n log n) O(n) ❤️
1157. Online Majority Element In Subarray Go Hard O(log n) O(n) ❤️