这是我第一题AC的线段树

题目简述： 有N个整数，Q次操作，每次操作为询问一个区间[a, b]内数的和(0号操作)或者把一个区间内的数全部加上v(1号操作)

线段树求解即可。

#include <cstdio> #include <algorithm> using std::min; using std::max; #define L(no) ((no) << 1) #define R(no) (L(no) | 1) #define PLUSTAG(no, val) plustag[no] += val, query[no] += val*(rb[no]-lb[no]+1) const int MAXN = 400001; int lb[MAXN], rb[MAXN], query[MAXN], ans, plustag[MAXN]; int sum(int a, int b) {return a + b;} void build(int no, int l, int r) {int mid = l + r >> 1;lb[no] = l;rb[no] = r;if(l == r) scanf("%d", &query[no]);else {build(L(no), l, mid);build(R(no), mid + 1, r);query[no] = query[L(no)] + query[R(no)];} } void getval(int no, int l, int r, int(*func)(int, int), int* key) {int mid = lb[no] + rb[no] >> 1;if(l <= r && (lb[no] <= r&& rb[no] >= r || rb[no] >= l && lb[no] <= l)) {if(lb[no] == l && rb[no] == r) ans = func(ans, key[no]);else {if(plustag[no]) {PLUSTAG(L(no), plustag[no]);PLUSTAG(R(no), plustag[no]);plustag[no] = 0;}getval(L(no), l, min(mid, r), func, key);getval(R(no), max(l, mid + 1), r, func, key);}} } void plus(int no, int l, int r, int val) {int mid = lb[no] + rb[no] >> 1;if(l <= r && (lb[no] <= r&& rb[no] >= r || rb[no] >= l && lb[no] <= l)) {if(lb[no] == l && rb[no] == r) {PLUSTAG(no, val);}else {if(plustag[no]) {PLUSTAG(L(no), plustag[no]);PLUSTAG(R(no), plustag[no]);plustag[no] = 0;}query[no] += (r - l + 1) * val;plus(L(no), max(l, lb[no]), min(mid, r), val);plus(R(no), max(l, mid + 1), min(r, rb[no]), val);}} } int main() {int n, q, i, op, a, b, v;scanf("%d%d", &n, &q);build(1, 1, n);for(i = 1; i <= q; i++) {scanf("%d%d%d", &op, &a, &b);if(op == 0) {ans = 0;getval(1, a, b, sum, query);printf("%d\n", ans);}else {scanf("%d", &v);if(v != 0) plus(1, a, b, v);}}return 0; }

解释一下：query[]表示一个区间里面的和……然后左右半区间分别搞……1操作时Lazy优化是必须要加的（就是好像老师布置的作业等要交了再补……），然后，便过之。

问我为什么getval写函数指针？因为这是百搭函数……要求最大值传入max最小值传min求和传sum……

然后：就没有然后了。过之。

转载于:https://www.cnblogs.com/nealchen/p/4290085.html

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的这是我第一题AC的线段树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。