湖南东方红建设集团有限公司网站,编写网站的软件,廊坊公司快速建站,电脑有网但浏览器打不开网页文章目录参考文档题目线段树实现单点修改#xff0c;区间求值模板题目308. 二维区域和检索 - 可变区间修改#xff0c;区间求值1. 掉落的方块#xff08;区间开点#xff09;2. 维护序列3. 一个简单的问题24. 天际线问题动态开点1. 区间和个数(单点修改开点)问题以及注意事…
文章目录参考文档题目线段树实现单点修改区间求值模板题目308. 二维区域和检索 - 可变区间修改区间求值1. 掉落的方块区间开点2. 维护序列3. 一个简单的问题24. 天际线问题动态开点1. 区间和个数(单点修改开点)问题以及注意事项参考文档
线段树动态开点java 动态开点c 线段树leetcode题目
题目
题目知识点/注意点难度更新数组后处理求和查询线段树困难维护序列区间修改、求和困难掉落的方块右边区间-1困难leetcode 气球颜色变换右边区间-1leetcode 218.天际线右边区间-1困难leetcode 307. 区域和检索 - 数组可修改下标开始的位置困难leetcode 315. 计算右侧小于当前元素的个数保证r l困难leetcode 493. 翻转对离散化 / 动态开点困难leetcode 327. 区间和的个数离散化 / 动态开点困难
线段树实现 一般Push_down和push_up是需要手动实现的。注意下标从1开始build和使用的时候需要注意。动态开点的时候push_down和update会动态开点。使用的时候需要保证r l否则会出现各种问题。动态开点的时候需要保证(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, vectorintnums) {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;}vectorint fallingSquares(vectorvectorint positions) {vectorintans;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;}vectorint fallingSquares(vectorvectorint positions) {vectorintans;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 一个push_down是下推另一个是更新区间的sum和懒标记
4. 天际线问题
离散化扫描线右端点-1左端点仍旧可以作为起点。
class NumMatrix {
public:// 每一行使用一个线段树来维护static const int MAXN 8e4 4;static const int N 3e2 4;int sum[N][MAXN];vectorvectorintnums;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(vectorvectorint 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(vectorint nums, int low, int high) {int n nums.size();LL ans 0;vectorLLsum(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开始
