参考文档

线段树动态开点java
动态开点c++
线段树leetcode题目
线段树codeforce专题

题目

题目	知识点/注意点	难度
更新数组后处理求和查询	push_down应该是子区间的长度	困难
区间最大公约数	数论 +注意l, r	困难
子序列和的最大值	询问过程中，需要push_up	困难
维护序列	区间修改、求和	困难
699.掉落的方块	区间修改，求最大值	困难
4. 气球颜色变换	右边区间-1
218.天际线	右边区间-1	困难
307. 区域和检索 - 数组可修改	下标开始的位置	困难
315. 计算右侧小于当前元素的个数	保证r >= l	困难
493. 翻转对	离散化 / 动态开点	困难
327. 区间和的个数	离散化 / 动态开点	困难
range模块	注意push_down设计	困难
我的日程安排	差分/线段树	困难
矩形面积2	天际线的进化版
题解	困难

亚特兰蒂斯	就是矩形的面积2

线段树实现

一般Push_down和push_up是需要手动实现的。
注意下标从1开始，build和使用的时候需要注意。
动态开点的时候，push_down会动态开点，32位开4e6。
使用的时候，需要保证r >= l，否则会出现各种问题。
动态开点的时候，需要保证(l, r)的范围包含全部点。
动态开点的时候，注意long long的使用。
动态开点的时候，idx = root = 1，那么可以直接使用push_down更新。应用于区间
idx = root = 0,那么应该判断if (!u) u = ++idx; 应用于单点。加上&
不要把l, r放在Node中，要不然Build的时候，每次需要更改。

单点修改，区间求值

模板题目

    static const int maxn = 4e5 + 4;int sum[maxn];int n;void push_up(int u) {sum[u] = sum[u << 1] + sum[u << 1 | 1];}void build(int u, int l, int r, vector<int>&nums) {if (l == r) {sum[u] = nums[l - 1];return ;}int mid = (l + r) >> 1;build(u << 1, l, mid, nums);build(u << 1 | 1, mid + 1, r, nums);push_up(u);}void update(int u, int l, int r, int p, int x) {if (p == l && l == r) {sum[u] = x;return ;}int mid = (l + r) >> 1;if (p <= mid) update(u << 1, l, mid, p, x);else update(u << 1 | 1, mid + 1, r, p, x);push_up(u);}int query(int u, int l, int r, int L, int R) {if (L <= l && r <= R) {return sum[u];}int mid = (l + r) >> 1;int ans = 0;if (L <= mid) ans = query(u << 1, l, mid, L, R);if (R > mid) ans += query(u << 1 | 1, mid + 1, r, L, R);return ans; }

308. 二维区域和检索 - 可变

class Solution {
public:// 加是不行的。为什么呢？因为区间[l, r]上的高度不统一。static const int N = 1e6 + 10;int maxh[N], lc[N], rc[N], idx = 0, root = 0; //  root应该写成全局变量,int lazy[N];// int add[N];         // 区间同时增加高度不行void push_up(int u) {maxh[u] = max(maxh[lc[u]], maxh[rc[u]]);}// 将区间，改编成add_h。如果没有区间就开点void push_down(int &u, int x) {if (!u) u = ++idx;                // push_down的时候也需要创建新的lazy[u] = maxh[u] = x;}// 懒标记下推void push_down(int u) {// if (add[u] == 0) return ;if (lazy[u] == 0) return ;push_down(lc[u], lazy[u]);push_down(rc[u], lazy[u]);lazy[u] = 0;                     // 清除懒标记}// [L, R]增加add_x， 需要加上引用，让lc和rc指向正确位置。void update(int &u, int l, int r, int L, int R, int add_x) {if (u == 0) u = ++idx;           // 给儿子创建一个新的点if (L <= l && r <= R) {push_down(u, add_x);// printf("add_x = %d\n", add_x);return ;}push_down(u);int mid = (l + r) >> 1;// printf("mid = %d l = %d r = %d, L = %d, R = %d\n", mid, l, r, L, R);if (L <= mid) update(lc[u], l, mid, L, R, add_x);if (R > mid) update(rc[u], mid + 1, r, L, R, add_x);push_up(u);                     // 没有传递u, 所以u不会变}// 询问，不用加引用int query(int u, int l, int r, int L, int R) {if (u == 0) return 0;           // 如果没更新这个区间直接返回if (L <= l && r <= R) {return maxh[u];}push_down(u);int mid = (l + r) >> 1;int maxv = 0;// printf("%d %d %d %d %d\n", mid, l, r, L, R);if (L <= mid) maxv = query(lc[u], l, mid, L, R);if (R > mid) maxv = max(maxv, query(rc[u], mid + 1, r, L, R));return maxv;}vector<int> fallingSquares(vector<vector<int>>& positions) {vector<int>ans;for (auto vec : positions) {int l = vec[0], r = vec[0] + vec[1] - 1, z = vec[1];int cur = query(root, 1, 1e9, l, r);// printf("cur = %d\n", cur);update(root, 1, 1e9, l, r, z + cur);ans.push_back(maxh[1]);}return ans;}
};

区间修改，区间求值

1. 掉落的方块（区间开点）

大区间

少查询

动态开点: 使用指针的进行开点

离散化

int x = info[0], h = info[1], cur = query(1, 1, N, x, x + h - 1);

查询 – [x, x + h - 1]

修改 – [x, x + h - 1, cur + h]

当前的最大值就是tr[1].val

class Solution {
public:// 加是不行的。为什么呢？因为区间[l, r]上的高度不统一。static const int N = 1e6 + 10;int maxh[N], lc[N], rc[N], idx = 0, root = 0; //  root应该写成全局变量,int lazy[N];// int add[N];         // 区间同时增加高度不行void push_up(int u) {maxh[u] = max(maxh[lc[u]], maxh[rc[u]]);}// 将区间，改编成add_h。如果没有区间就开点void push_down(int &u, int x) {if (!u) u = ++idx;                // push_down的时候也需要创建新的lazy[u] = maxh[u] = x;}// 懒标记下推void push_down(int u) {// if (add[u] == 0) return ;if (lazy[u] == 0) return ;push_down(lc[u], lazy[u]);push_down(rc[u], lazy[u]);lazy[u] = 0;                     // 清除懒标记}// [L, R]增加add_xvoid update(int &u, int l, int r, int L, int R, int add_x) {if (u == 0) u = ++idx;           // 给儿子创建一个新的点if (L <= l && r <= R) {push_down(u, add_x);// printf("add_x = %d\n", add_x);return ;}push_down(u);int mid = (l + r) >> 1;// printf("mid = %d l = %d r = %d, L = %d, R = %d\n", mid, l, r, L, R);if (L <= mid) update(lc[u], l, mid, L, R, add_x);if (R > mid) update(rc[u], mid + 1, r, L, R, add_x);push_up(u);                     // 没有传递u, 所以u不会变}int query(int &u, int l, int r, int L, int R) {if (u == 0) return 0;           // 如果没更新这个区间直接返回if (L <= l && r <= R) {return maxh[u];}push_down(u);int mid = (l + r) >> 1;int maxv = 0;// printf("%d %d %d %d %d\n", mid, l, r, L, R);if (L <= mid) maxv = query(lc[u], l, mid, L, R);if (R > mid) maxv = max(maxv, query(rc[u], mid + 1, r, L, R));return maxv;}vector<int> fallingSquares(vector<vector<int>>& positions) {vector<int>ans;for (auto vec : positions) {int l = vec[0], r = vec[0] + vec[1] - 1, z = vec[1];int cur = query(root, 1, 1e9, l, r);// printf("cur = %d\n", cur);update(root, 1, 1e9, l, r, z + cur);ans.push_back(maxh[1]);}return ans;}
};

问题1：为什么动态开点不判断u是否为空？询问直接返回就行了，更新的时候需要判断。
问题2：直接把val赋值成为add，是否都是这样？还是仅仅是这个题目这样？仅仅这个题目这样。

2. 维护序列

调试技巧

首先判断build是否成功
其次判断询问是否成功
最后根据根节点的信息判断更新是否成功。
push_down和push_up可以输出前后的sum[u]进行判断

3. 一个简单的问题2

java代码再acwnig的java代码上。

long的使用
两个push_down
1. 一个push_down是下推
2. 另一个是更新区间的sum和懒标记

4. 天际线问题

离散化
扫描线
右端点-1，左端点仍旧可以作为起点。

class NumMatrix {
public:// 每一行使用一个线段树来维护static const int MAXN = 8e4 + 4;static const int N = 3e2 + 4;int sum[N][MAXN];vector<vector<int>>nums;int m, n;void push_up(int row, int u) {sum[row][u] = sum[row][u << 1] + sum[row][u << 1 | 1];}void build(int row, int u, int l, int r) {if (l == r) {sum[row][u] = nums[row][l - 1];return ;}int mid = (l + r) >> 1;// printf("%d %d %d\n", l, r, mid);build(row, u << 1, l, mid);build(row, u << 1 | 1, mid + 1, r);push_up(row, u);}void update(int u, int l, int r, int row, int col, int x) {if (l == r && col == l) {       // l == r的时候col一定等于lsum[row][u] = x;return ;}int mid = (l + r) >> 1;if (col <= mid) update(u << 1, l, mid, row, col, x);else update(u << 1 | 1, mid + 1, r, row, col, x);push_up(row, u);}int query(int u, int l, int r, int row, int L, int R) {if (L <= l && r <= R) {return sum[row][u];}int mid = (l + r) >> 1;int ans = 0;if (L <= mid) ans += query(u << 1, l, mid, row, L, R);if (R > mid) ans += query(u << 1 | 1, mid + 1, r, row, L, R);return ans; }NumMatrix(vector<vector<int>>& matrix) {this->nums = matrix;m = nums.size();n = nums[0].size();for (int i = 0; i < m; i++) {build(i, 1, 1, n);// printf("%d\n", sum[i][1]);}}void update(int row, int col, int val) {col++;update(1, 1, n, row, col, val);}int sumRegion(int row1, int col1, int row2, int col2) {int ans = 0;col1++, col2++;for (int i = row1; i <= row2; i++) {ans += query(1, 1, n, i, col1, col2);}return ans;}
};/*** Your NumMatrix object will be instantiated and called as such:* NumMatrix* obj = new NumMatrix(matrix);* obj->update(row,col,val);* int param_2 = obj->sumRegion(row1,col1,row2,col2);*/

动态开点

1. 区间和个数(单点修改开点)

注意求最大和最小值的过程
注意前缀和为0的情况需要加入进去。而前缀和为0的时候，不用考虑query，因为一定为0，所有的点都是0。

  typedef long long LL;static const int N = 4e6 + 10;              // 开太小了也爆栈LL add[N];int idx = 0, root = 0, lc[N], rc[N];void push_up(int u) {add[u] = add[lc[u]] + add[rc[u]];       // 如果使用node，可能会出现点不存在的情况，但是这里并不会，因为add[0] = 0;}// 单点修改开点void update(int &u, LL l, LL r, LL p) {if (!u) u = ++idx;// add[u]++;                               // 直接相当于push_up了if (l == r && l == p) {add[u] += 1;return ;} LL mid = (l + r) >> 1;if (p <= mid) update(lc[u], l, mid, p);else update(rc[u], mid + 1, r, p);push_up(u);}LL query(int u, LL l, LL r, LL L, LL R) {if (!u) return 0;if (L <= l && r <= R) return add[u];LL mid = (l + r) >> 1;LL ans = 0;if (L <= mid) ans += query(lc[u], l, mid, L, R);if (R > mid) ans += query(rc[u], mid + 1, r, L, R);return ans;}int countRangeSum(vector<int>& nums, int low, int high) {int n = nums.size();LL ans = 0;vector<LL>sum(n + 1);sum[0] = 0;memset(lc, 0, sizeof lc);memset(rc, 0 ,sizeof rc);for (int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + nums[i - 1];}LL minv = LLONG_MAX, maxv = LLONG_MIN;for (LL x: sum) {minv = min({minv, x, x - high});maxv = max({maxv, x, x - high});}// cout << minv << " " << maxv << endl;for (LL x: sum) {LL l = x - high, r = x - low;// cout <<x << " " << l << " " << r << endl;ans += query(root, minv, maxv, l, r);// cout << query(root, minv, maxv, l, r) << endl;update(root, minv, maxv, x);}return ans;}
};

2. range模块(区间开点)

class RangeModule {static final int maxn = (int)4e6 + 10;static final int MAXN = (int)1e9;boolean [] c, add;int[] lc, rc;int idx = 1, root = 1;public void push_up(int u) {c[u] = c[lc[u]] & c[rc[u]];}public void push_down(int u, boolean flag) {c[u] = flag;                       add[u] = true;                  // 不是取反。}public void push_down(int u) {if (lc[u] == 0) lc[u] = ++idx;  // 动态开点if (rc[u] == 0) rc[u] = ++idx;if (!add[u]) return ;push_down(lc[u], c[u]);         // 父亲区间当时是什么，他就是什么push_down(rc[u], c[u]);add[u] = false;}// update的时候动态开点，push_down的时候，以及每次访问的时候。public void update(int u, int l, int r, int L, int R, boolean flag) {if (L <= l && r <= R) {push_down(u, flag);return ;}push_down(u);int mid = (l + r) >> 1;if (L <= mid) update(lc[u], l, mid, L, R, flag);if (R > mid) update(rc[u], mid + 1, r ,L, R, flag);push_up(u);}public boolean query(int u, int l, int r, int L, int R) {if (u == 0) return false;           // 没被访问过，说明没被监听if (L <= l && r <= R) {return c[u];}push_down(u);int mid = (l + r) >> 1;boolean ans = true;if (L <= mid) ans &= query(lc[u], l, mid, L, R);if (R > mid) ans &= query(rc[u], mid + 1, r ,L, R);return ans;}public RangeModule() {c = new boolean[maxn];add = new boolean[maxn];lc = new int[maxn];rc = new int[maxn];}public void addRange(int left, int right) {update(root, 1, MAXN, left, right - 1, true);}public boolean queryRange(int left, int right) {return query(root, 1, MAXN, left, right - 1);}public void removeRange(int left, int right) {update(root, 1, MAXN, left, right - 1, false);}
}/*** Your RangeModule object will be instantiated and called as such:* RangeModule obj = new RangeModule();* obj.addRange(left,right);* boolean param_2 = obj.queryRange(left,right);* obj.removeRange(left,right);*/

3. 矩形面积

package dataStructure;import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.*;/*** @author: Zekun Fu* @date: 2023/2/25 10:01* @Description: 扫描线* 1. 扫描线很难扩展* 2.* 扫描线：左边加上，右边减去。* x 排序** 区间修改，区间查询* 性质：* 1. 永远只考虑根节点的信息 -> 查询不用push_down了。* 2. 操作都是成对出现， 且先加后减-> 修改的时候不用push_down了*              减法的时候*                  1. 恰好成对出现***              加法操作：*                  1. cnt > 0： 不push_down也不用影响结果*                  2. cnt == 0: 懒标记不用下推** 由于有double，所以离散化，用unique来做**  线段树*  1. 存储线段， yl-1 表示 yl-1到y, 所以需要把yl到yr-1进行 + diff就行了*  1.1 修改区间，就是修改纵坐标的区间。*  1.2 求和，只求头的和*  2. cover和*  3. segment：离散化 + 扫描线的产物*  4. ys, y坐标离散化的产物，保留了。*  5. push_up操作*      1. 如果cover等于1，说明完全被覆盖，直接就是当前区间的代表现段总长。*      2. 如果**/
public class Acwing_247 {private static double[] ys, len;private static int[] cover;private static Segment[] seg;private static int idx;private static void init(int n) {int m = n * 2;ys = new double[m];len = new double[m * 4];cover = new int[m * 4];seg = new Segment[m];idx = 0;}// 使用double进行离散化，很困难啊。// 如果单单使用mp进行离散化，那么离散化之后的高度，就不知道等于多少了// 这里使用双向映射，就可以知道idx对应的高度是多少了。private static void push_up (int u, int l, int r) {if (cover[u] == 1) {len[u] = ys[r + 1] - ys[l];} else if (l == r) len[u] = 0;      // 因为没有push_down,所以碰见叶子结点，从push_up中修改成0else len[u] = len[u << 1] + len[u << 1 | 1];}private static void update(int u, int l, int r, int L, int R, int d) {if (L > R) throw new NoSuchElementException(String.format("输入应该保证L <= R但是给定[L, R] = [%d, %d]", L, R));if (L > r || R < l) throw new NoSuchElementException(String.format("区间[L, R]应该在区间[l, r]之内但是给定[L, R] = [%d %d], [l, r] = [%d, %d]", L, R, l, r));if (L <= l && r <= R) {cover[u] += d;push_up(u, l, r);           // push_up代替了push_downreturn ;}int mid = l + r >> 1;if (L <= mid) update(u << 1, l, mid, L, R, d);if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, d);push_up(u, l, r);}private static class Segment implements Comparable<Segment>{public double x, y1, y2;public int diff;@Overridepublic int compareTo(Segment o) {return Double.compare(x, o.x);}public Segment(double x, double y1, double y2, int diff) {this.x = x;this.y1 = y1;this.y2 = y2;this.diff = diff;}}private static double[] unique(double []sortNums) {double eps = 1e-9;int n = sortNums.length;int j = 0;for(int i = 0;i < n;i++) {if (i == 0 || Math.abs(sortNums[i] - sortNums[i - 1]) > eps) {sortNums[j] = sortNums[i];j++;}}double[] ans = new double[j];for (int i = 0; i < j; i++) {ans[i] = sortNums[i];}return ans;}public static int find(double aIndex){double eps = 1e-9;int l = 0;int r = ys.length;while(l < r){int mid = l + r >>1;if(ys[mid] - aIndex >= eps) r = mid;else l = mid + 1;}return l - 1;}public static void main(String[] args) throws Exception{int T = 1;BufferedReader in = new BufferedReader(new InputStreamReader(System.in));BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));int n = Integer.parseInt(in.readLine().split(" ")[0]);while (n != 0) {init(n);String[] input;for (int i = 0, j = 0, k = 0; i < n; i++) {input = in.readLine().split(" ");double x1 = Double.parseDouble(input[0]);double y1 = Double.parseDouble(input[1]);double x2 = Double.parseDouble(input[2]);double y2 = Double.parseDouble(input[3]);seg[j ++] = new Segment(x1, y1, y2, 1);seg[j ++] = new Segment(x2, y1, y2, -1);ys[k++] = y1;ys[k++] = y2;}// 离散化, 为了获取idx对应的高度，双向映射Arrays.sort(ys);Arrays.sort(seg);ys = unique(ys);idx = ys.length;int m = 2 * n;double res = 0 ;for (int i = 0; i < m; i++) {if (i != 0) res += len[1] * (seg[i].x - seg[i - 1].x);int l = find(seg[i].y1), r = find(seg[i].y2);update(1,0, idx - 1, l, r - 1, seg[i].diff);}out.write(String.format("Test case #%d\n", T++));out.write(String.format("Total explored area: %.2f\n\n", res));n = Integer.parseInt(in.readLine().split(" ")[0]);}out.flush();out.close();in.close();}
}

使用Map进行离散化


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;/*** @author: Zekun Fu* @date: 2023/2/25 10:01* @Description: 扫描线* 1. 扫描线很难扩展* 2.* 扫描线：左边加上，右边减去。* x 排序** 区间修改，区间查询* 性质：* 1. 永远只考虑根节点的信息 -> 查询不用push_down了。* 2. 操作都是成对出现， 且先加后减-> 修改的时候不用push_down了*              减法的时候*                  1. 恰好成对出现***              加法操作：*                  1. cnt > 0： 不push_down也不用影响结果*                  2. cnt == 0: 懒标记不用下推**  线段树*  1. 存储线段， yl-1 表示 yl-1到y, 所以需要把yl到yr-1进行 + diff就行了*  1.1 修改区间，就是修改纵坐标的区间。*  1.2 求和，只求头的和*  2. cover和*  3. segment：离散化 + 扫描线的产物*  4. ys, y坐标离散化的产物，保留了。*  5. push_up操作*      1. 如果cover等于1，说明完全被覆盖，直接就是当前区间的代表现段总长。*      2. 如果**/
public class Main {private static double[] ys, len;private static int[] cover;private static Segment[] seg;private static HashMap<Double, Integer>mp;private static HashMap<Integer, Double>height;private static int idx;private static void init(int n) {int m = n * 2;ys = new double[m];len = new double[m * 4];cover = new int[m * 4];seg = new Segment[m];mp = new HashMap<>();height = new HashMap<>();idx = 0;}// 如果单单使用mp进行离散化，那么离散化之后的高度，就不知道等于多少了// 这里使用双向映射，就可以知道idx对应的高度是多少了。private static void push_up (int u, int l, int r) {if (cover[u] >= 1) {if (!height.containsKey(r + 1))throw new NoSuchElementException(String.format("没有r = %d这个key。r应该是现段左端点，%d是否越界了！", r + 1, r + 1));if (!height.containsKey(l))throw new NoSuchElementException(String.format("L = %d太小了", l));len[u] = height.get(r + 1) - height.get(l);} else if (l == r) len[u] = 0;      // 因为没有push_down,所以碰见叶子结点，从push_up中修改成0else len[u] = len[u << 1] + len[u << 1 | 1];}private static void update(int u, int l, int r, int L, int R, int d) {if (L > R) throw new NoSuchElementException(String.format("输入应该保证L <= R但是给定[L, R] = [%d, %d]", L, R));if (L > r || R < l) throw new NoSuchElementException(String.format("区间[L, R]应该在区间[l, r]之内但是给定[L, R] = [%d %d], [l, r] = [%d, %d]", L, R, l, r));if (L <= l && r <= R) {cover[u] += d;push_up(u, l, r);           // push_up代替了push_downreturn ;}int mid = l + r >> 1;if (L <= mid) update(u << 1, l, mid, L, R, d);if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, d);push_up(u, l, r);}private static class Segment implements Comparable<Segment>{public double x, y1, y2;public int diff;@Overridepublic int compareTo(Segment o) {return Double.compare(x, o.x);}public Segment(double x, double y1, double y2, int diff) {this.x = x;this.y1 = y1;this.y2 = y2;this.diff = diff;}}public static void main(String[] args) throws Exception{int T = 1;BufferedReader in = new BufferedReader(new InputStreamReader(System.in));BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));int n = Integer.parseInt(in.readLine().split(" ")[0]);while (n != 0) {init(n);String[] input;for (int i = 0, j = 0, k = 0; i < n; i++) {input = in.readLine().split(" ");double x1 = Double.parseDouble(input[0]);double y1 = Double.parseDouble(input[1]);double x2 = Double.parseDouble(input[2]);double y2 = Double.parseDouble(input[3]);seg[j ++] = new Segment(x1, y1, y2, 1);seg[j ++] = new Segment(x2, y1, y2, -1);ys[k++] = y1;ys[k++] = y2;}// 离散化, 为了获取idx对应的高度，双向映射Arrays.sort(ys);Arrays.sort(seg);int m = 2 * n;for (int i = 0; i < m; i++) {if (mp.containsKey(ys[i])) continue;mp.put(ys[i], ++idx);height.put(idx, ys[i]);}double res = 0 ;for (int i = 0; i < m; i++) {if (i != 0) res += len[1] * (seg[i].x - seg[i - 1].x);int l = mp.get(seg[i].y1), r = mp.get(seg[i].y2);update(1,1, idx, l, r - 1, seg[i].diff);}out.write(String.format("Test case #%d\n", T++));out.write(String.format("Total explored area: %.2f\n\n", res));n = Integer.parseInt(in.readLine().split(" ")[0]);}out.flush();out.close();in.close();}
}

4. 天际线

左加右减
同一批次处理
优先队列 + map找最大值

package leetcode.categories.dataStructure.xianduanshu;import leetcode.utils.ChangeToArrayOrList;
import leetcode.utils.PrintArrays;import java.lang.reflect.Array;
import java.util.*;/*** @author: Zekun Fu* @date: 2023/2/27 15:20* @Description: 天际线** 1. 扫描线* 2. 线段树*/
public class Leet218 {private class Segment implements Comparable<Segment>{public int x, y;public int diff;public Segment(int x, int y, int diff) {this.x = x;this.y = y;this.diff = diff;}@Overridepublic int compareTo(Segment o) {return Integer.compare(this.x, o.x);}}public List<List<Integer>> getSkyline(int[][] buildings) {int n = buildings.length;int m = n * 2;Segment[] seg = new Segment[m];for (int i = 0, j = 0; i < n; i++) {int[] build =  buildings[i];int x1 = build[0], x2 = build[1], h = build[2];seg[j++] = new Segment(x1, h, 1);seg[j++] = new Segment(x2, h, -1);}Arrays.sort(seg);List<List<Integer>> ans = new ArrayList<>();HashMap<Integer, Integer>mp = new HashMap<>();PriorityQueue<Integer>que = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {if (o1 > o2) return -1;                                     // 自动拆包else if (o1.equals(o2)) return 0;else return 1;}});que.add(0);mp.put(0, 1);int pre = 0;for (int i = 0; i < m; ) {int j = i;// 处理相同的边界while (j < m && seg[i].x == seg[j].x) {int h = seg[j].y, diff = seg[j].diff;if (mp.containsKey(h)) mp.put(h, mp.get(h) + diff);else mp.put(h, diff);// 入队if (mp.get(h) > 0) que.add(h);// 出队while (!que.isEmpty() && mp.getOrDefault(que.peek(), 0) == 0) que.poll();j++;}if (pre != que.peek()) {pre = que.peek();Integer[] tmp = new Integer[]{seg[i].x, pre};ans.add(Arrays.asList(tmp));}i = j;}return ans;}public static void main(String[] args) {Leet218 leet218 = new Leet218();String arr = "[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]";int[][]tmp = ChangeToArrayOrList.changeTo2DIntArray(arr);List<List<Integer>>list = leet218.getSkyline(tmp);for (List<Integer>t : list) {PrintArrays.print1DObjArray(t.toArray(new Integer[t.size()]));}}
}

package leetcode.categories.dataStructure.xianduanshu;import leetcode.utils.ChangeToArrayOrList;
import leetcode.utils.PrintArrays;import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;/*** @author: Zekun Fu* @date: 2023/2/27 16:13* @Description:* 天际线线段树解法*/
public class leet218_2 {private final int maxn = (int)4e6 + 5;private int[] lc, rc, maxv, flag;private int idx = 1, root = 1;          // 从push_down中开点，所以从1开始private void push_up(int u) {maxv[u] = Math.max(maxv[lc[u]], maxv[rc[u]]);}// 只有在完全包含这个区间的时候，才会进行push_down(u, x)操作。private void push_down(int u, int x) {maxv[u] = Math.max(maxv[u], x);flag[u] = Math.max(flag[u], x);}private void push_down(int u) {// 动态开点if (lc[u] == 0) lc[u] = ++idx;if (rc[u] == 0) rc[u] = ++idx;if (flag[u] == 0) return ;push_down(lc[u], flag[u]);push_down(rc[u], flag[u]);flag[u] = 0;}public void update(int u, int l, int r, int L, int R, int x) {if (L > R) throw new IllegalArgumentException(String.format("L = %d > R = %d!", L, R));if (L > r || R < l) throw new IllegalArgumentException(String.format("[L, R] = [%d %d] & [l, r] = [%d %d] == null", L, R, l, r));if (L <= l && r <= R) {push_down(u, x);return ;}push_down(u);int mid = (int)(((long)l + r) >> 1);if (L <= mid) update(lc[u], l, mid, L, R, x);if (R > mid) update(rc[u], mid + 1, r, L, R, x);push_up(u);}public int query(int u, int l, int r, int L, int R) {if (L > R) throw new IllegalArgumentException("L > R!");if (L > r || R < l) throw new IllegalArgumentException(String.format("[L, R] = [%d %d] & [l, r] = [%d %d] == null", L, R, l, r));if (u == 0) return 0;                                       // 没被访问，就一定没有值if (L <= l && r <= R) {return maxv[u];}push_down(u);int mid = (int)(((long)l + r) >> 1);int ans = 0;                                            // 注意是否long, 是否从0开始if (L <= mid) ans = query(lc[u], l, mid, L, R);if (R > mid) ans = Math.max(ans, query(rc[u], mid + 1, r, L, R));return ans;a}private void init() {this.flag = new int[maxn];this.maxv = new int[maxn];this.lc = new int[maxn];this.rc = new int[maxn];}public List<List<Integer>> getSkyline(int[][] buildings) {// 1. 线段树动态开点// 2. 对于每一个building，让区间[l, r - 1]整体修改成h// 3. 遍历所有的x// 4. 碰见最大值和前面不相同，就记录[x, cur]// 当前的最大高度取决于左边界的高度init();int maxv = Integer.MAX_VALUE;                   //[0, maxv]一定包含全部[0, maxv - 1]List<Integer>xs = new ArrayList<>();for (int[] build : buildings) {update(root, 0, maxv, build[0], build[1] - 1, build[2]);xs.add(build[0]);xs.add(build[1]);}int pre = 0;List<List<Integer>> ans = new ArrayList<>();Collections.sort(xs);for (int x : xs) {int h = query(root, 0, maxv, x, x);Integer[] tmp = new Integer[]{x, h};if (h != pre) ans.add(Arrays.asList(tmp));pre = h;}return ans;}public static void main(String[] args) {leet218_2 leet218_2 = new leet218_2();String arr = "[[0,2,3],[2,5,3]]";int[][]tmp = ChangeToArrayOrList.changeTo2DIntArray(arr);List<List<Integer>>list = leet218_2.getSkyline(tmp);for (List<Integer>t : list) {PrintArrays.print1DObjArray(t.toArray(new Integer[t.size()]));}}
}

调试技巧

query和add分别加上两句话防止使用出错!

query() {if (L > R) throw new NoSuchElementException("区间L 应该 小于R");if (L > r || R < l) throw new NoSuchElementException("区间[L, R]和区间[l, r]应该有交集![可能是l，r不能包含所有区间！]");
}
update() {if (p < l || p > r) throw new NoSuchElementException("p越界了,p应该在区间中");
}