2.18 ✅ Segment Tree

Segment Tree #

  • 线段树的经典数组实现写法。将合并两个节点 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:直接取根节点的值
No.TitleSolutionDifficultyTimeComplexitySpaceComplexityFavoriteAcceptance
0218The Skyline ProblemGoHardO(n log n)O(n)❤️41.9%
0307Range Sum Query - MutableGoMediumO(1)O(n)40.7%
0315Count of Smaller Numbers After SelfGoHardO(n log n)O(n)42.6%
0327Count of Range SumGoHardO(n log n)O(n)❤️35.8%
0493Reverse PairsGoHardO(n log n)O(n)30.9%
0699Falling SquaresGoHardO(n log n)O(n)❤️44.7%
0715Range ModuleGoHardO(log n)O(n)❤️44.6%
0729My Calendar IGoMedium56.8%
0732My Calendar IIIGoHardO(log n)O(n)❤️71.5%
0850Rectangle Area IIGoHardO(n log n)O(n)❤️53.9%
1157Online Majority Element In SubarrayGoHardO(log n)O(n)❤️41.8%
1649Create Sorted Array through InstructionsGoHard37.5%
——————————————————————-——-—————-—————————-————-————-

⬅️上一页

下一页➡️

Calendar Apr 8, 2023
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者