线段树总结

参考文档

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

题目

题目	知识点/注意点	难度
更新数组后处理求和查询	线段树	困难
维护序列	区间修改、求和	困难
掉落的方块	右边区间-1	困难
leetcode 气球颜色变换	右边区间-1
leetcode 218.天际线	右边区间-1	困难
leetcode 307. 区域和检索 - 数组可修改	下标开始的位置	困难
leetcode 315. 计算右侧小于当前元素的个数	保证r >= l	困难
leetcode 493. 翻转对	离散化 / 动态开点	困难
leetcode 327. 区间和的个数	离散化 / 动态开点	困难

线段树实现

1. 一般Push_down和push_up是需要手动实现的。
2. 注意下标从1开始，build和使用的时候需要注意。
3. 动态开点的时候，push_down和update会动态开点。
4. 使用的时候，需要保证r >= l，否则会出现各种问题。
5. 动态开点的时候，需要保证(l, r)的范围包含全部点。

单点修改，区间求值

模板题目

    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. 维护序列

调试技巧

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

3. 一个简单的问题2

java代码再acwnig的java代码上。

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

4. 天际线问题

1. 离散化
2. 扫描线
3. 右端点-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;}
};

问题以及注意事项

1. 天际线和方块的问题中，为什么需要右端点-1，而不是左端点 + 1呢？
2. 具体的调试技巧，看上面的维护序列。
3. 注意使用的时候，区间从1开始，