LeetCode 分类刷题 —— Segment Tree

2019-09-29  本文已影响0人  一缕殇流化隐半边冰霜

Segment Tree 的 Tips:

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

  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) ❤️
上一篇 下一篇

猜你喜欢

热点阅读