首页 > 代码库 > 线段树 & 题目
线段树 & 题目
首先说下我写的线段树吧。
我是按照线段树【完全版】那个人的写法来写的，因为网上大多数题解都是按照他的写法来写。
确实比较飘逸，所以就借用了。
节点大小是maxn是4倍，准确来说是大于maxn的2^x次方的最小值的两倍。因为要pushUp的时候会去到一些无用的节点。
就是在叶子节点的时候还pushUp了的话，要去到两个无用的节点，所以是最小值的两倍。
lson 和 rson 用宏定义写了。因为是固定的量。
线段树不必保存自身的区间，因为一边传递过去的时候，在函数里就有区间表示，无谓开多些无用的变量。
pushUp函数，更新当前节点cur的值，其实就是，线段树一般都是处理完左右孩子，然后再递归更新父亲的嘛，这个pushUp函数就是用来更新父亲的。感觉不用这个函数更加清楚明了。
pushDown函数，在lazy--upDate的时候有用，作用是把延迟标记更新到左右节点。
1 #define lson L, mid, cur << 1 2 #define rson mid + 1, R, cur << 1 | 1 3 void pushUp(int cur) { 4 sum[cur] = sum[cur << 1] + sum[cur << 1 | 1]; 5 } 6 void pushDown(int cur, int total) { 7 if (add[cur]) { 8 add[cur << 1] += add[cur]; //传递去左右孩子 9 add[cur << 1 | 1] += add[cur]; // val >> 1 相当于 val / 210 sum[cur << 1] += add[cur] * (total - (total >> 1)); //左孩子有多少个节点11 sum[cur << 1 | 1] += add[cur] * (total >> 1); //一共控制11个，则右孩子有5个12 add[cur] = 0;13 }14 }15 void build(int L, int R, int cur) {16 if (L == R) {17 sum[cur] = a[L];18 return;19 }20 int mid = (L + R) >> 1;21 build(lson);22 build(rson);23 pushUp(cur);24 }25 void upDate(int begin, int end, int val, int L, int R, int cur) {26 if (L >= begin && R <= end) {27 add[cur] += val; 28 sum[cur] += val * (R - L + 1); //这里加了一次，后面pushDown就只能用add[cur]的29 return;30 }31 pushDown(cur, R - L + 1); //这个是必须的，因为下面的pushUp是直接等于的32 //所以要先把加的，传递去右孩子，然后父亲又调用pushUp，才能保证正确性。33 int mid = (L + R) >> 1; //一直分解的是大区间，开始时是[1, n]这个区间。34 if (begin <= mid) upDate(begin, end, val, lson); //只要区间涉及，就必须更新35 if (end > mid) upDate(begin, end, val, rson);36 pushUp(cur);37 }38 int query(int begin, int end, int L, int R, int cur) {39 if (L >= begin && R <= end) {40 return sum[cur];41 }42 pushDown(cur, R - L + 1);43 int ans = 0, mid = (L + R) >> 1;44 if (begin <= mid) ans += query(begin, end, lson); //只要区间涉及，就必须查询45 if (end > mid) ans += query(begin, end, rson);46 return ans;47 }
关于成段更新时的upDate函数，中途的pushDown是不能省的，可以看看第三题然后结合我给的数据（数据是poj的大牛发出来的，不是我想的。）关键就在于pushUp函数是直接等于的，你不pushDown，然后pushUp，就会把以前的增加值给抹杀了
敌兵布阵
单点更新，区间求和
http://acm.hdu.edu.cn/showproblem.php?pid=1166
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>#define lson L, mid, cur << 1#define rson mid + 1, R, cur << 1 | 1const int maxn = 50000 + 20;int sum[maxn << 2];int a[maxn];void pushUp(int cur) { //更新当前这个节点的信息 sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];}void build(int L, int R, int cur) { if (L == R) { sum[cur] = a[L]; return; } int mid = (L + R) >> 1; build(lson); build(rson); pushUp(cur);}void upDate(int pos, int val, int L, int R, int cur) { if (L == pos && R == pos) { sum[cur] += val; return; } int mid = (L + R) >> 1; if (pos <= mid) upDate(pos, val, lson); else upDate(pos, val, rson); pushUp(cur);}int query(int begin, int end, int L, int R, int cur) { //[L, R]大区间, [begin, end]查询区间 if (L >= begin && R <= end) { //这个大区间是待查区间的子集 return sum[cur]; } int mid = (L + R) >> 1; int ans = 0; if (begin <= mid) ans += query(begin, end, lson); if (end > mid) ans += query(begin, end, rson); return ans;}int f;void work() { printf("Case %d:\n", ++f); int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } build(1, n, 1); char cmd[111]; while (scanf("%s", cmd) != EOF && cmd[0] != ‘E‘) { int a, b; scanf("%d%d", &a, &b); if (cmd[0] == ‘Q‘) { printf("%d\n", query(a, b, 1, n, 1)); } else if (cmd[0] == ‘A‘) { upDate(a, b, 1, n, 1); } else { upDate(a, -b, 1, n, 1); } } return;}int main() {#ifdef local freopen("data.txt","r",stdin);#endif int t; scanf("%d", &t); while (t--) { work(); } return 0;}
I Hate It
单点更新，区间最值
http://acm.hdu.edu.cn/showproblem.php?pid=1754
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>#define lson L, mid, cur << 1#define rson mid + 1, R, cur << 1 | 1const int maxn = 200000 + 20;int mx[maxn << 2];int a[maxn];void pushUp(int cur) { mx[cur] = max(mx[cur << 1], mx[cur << 1 | 1]);}void build(int L, int R, int cur) { if (L == R) { mx[cur] = a[L]; //就是自己 return; } int mid = (L + R) >> 1; build(lson); build(rson); pushUp(cur);}void upDate(int pos, int val, int L, int R, int cur) { if (L == pos && R == pos) { //精确到这一个点 mx[cur] = val; return; } int mid = (L + R) >> 1; if (pos <= mid) upDate(pos, val, lson); else upDate(pos, val, rson); pushUp(cur);}int query(int begin, int end, int L, int R, int cur) { if (L >= begin && R <= end) { return mx[cur]; } int mid = (L + R) >> 1; int ans = 0; if (begin <= mid) ans = query(begin, end, lson); //区间有涉及，级要查询 if (end > mid) ans = max(ans, query(begin, end, rson)); return ans;}int n, m;void work() { for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } build(1, n, 1); for (int i = 1; i <= m; ++i) { char str[11]; int b, c; scanf("%s%d%d", str, &b, &c); if (str[0] == ‘Q‘) { printf("%d\n", query(b, c, 1, n, 1)); } else upDate(b, c, 1, n, 1); }}int main() {#ifdef local freopen("data.txt","r",stdin);#endif while (scanf("%d%d", &n, &m) != EOF) { work(); } return 0;}
成段更新，区间查询总和，这题记得用LL，
给个数据
10 221 2 3 4 5 6 7 8 9 10Q 4 4C 1 10 3C 6 10 3C 6 9 3C 8 9 -100C 7 9 3C 7 10 3C 1 10 3Q 6 10Q 6 9Q 8 9Q 7 9Q 7 10Q 1 10Q 2 4C 3 6 3Q 9 9Q 1 1Q 5 5Q 6 6Q 7 7Q 6 8ans4-82-104-147-122-100-3727-737142125-28
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#define lson L, mid, cur << 1#define rson mid + 1, R, cur << 1 | 1const int maxn = 100000 + 20;LL sum[maxn << 2];LL add[maxn << 2];int a[maxn];void pushUp(int cur) { sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];}void pushDown(int cur, int total) { if (add[cur]) { add[cur << 1] += add[cur]; add[cur << 1 | 1] += add[cur]; // val >> 1 相当于 val / 2 sum[cur << 1] += add[cur] * (total - (total >> 1)); //左孩子有多少个节点 sum[cur << 1 | 1] += add[cur] * (total >> 1); //一共控制11个，则右孩子有5个 add[cur] = 0; }}void build(int L, int R, int cur) { if (L == R) { sum[cur] = a[L]; return; } int mid = (L + R) >> 1; build(lson); build(rson); pushUp(cur);}void upDate(int begin, int end, LL val, int L, int R, int cur) { if (L >= begin && R <= end) { add[cur] += val;//这里加了一次，后面pushDown就只能用add[cur]的 sum[cur] += val * (R - L + 1); //控制的节点数目 return; } pushDown(cur, R - L + 1); int mid = (L + R) >> 1; if (begin <= mid) upDate(begin, end, val, lson); if (end > mid) upDate(begin, end, val, rson); pushUp(cur);}LL query(int begin, int end, int L, int R, int cur) { if (L >= begin && R <= end) { return sum[cur]; } pushDown(cur, R - L + 1); LL ans = 0, mid = (L + R) >> 1; if (begin <= mid) ans += query(begin, end, lson); if (end > mid) ans += query(begin, end, rson); return ans;}void work() { int n, q; scanf("%d%d", &n, &q); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } build(1, n, 1); char str[11]; for (int i = 1; i <= q; ++i) { scanf("%s", str); int L, R, val; if (str[0] == ‘Q‘) { scanf("%d%d", &L, &R); printf("%I64d\n", query(L, R, 1, n, 1)); } else { scanf("%d%d%d", &L, &R, &val); upDate(L, R, val, 1, n, 1); } } return;}int main() {#ifdef local freopen("data.txt","r",stdin);#endif work(); return 0;}
线段树 & 题目
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。