#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5;
int n, q;
int a[N + 5], tree[(N + 5) * 4], lzytag[(N + 5) * 4];
int ls(int x) { return x << 1;}
int rs(int x) { return x << 1 | 1;}
void pushup(int x) {
tree[x] = tree[ls(x)] + tree[rs(x)];
}
void build(int x, int xl, int xr) {
lzytag[x] = 0;
if(xl == xr) { tree[x] = tree[xl]; return;}
int mid = (xl + xr) / 2;
build(ls(x), xl, mid); build(rs(x), mid + 1, xr);
}
void addtag(int x, int xl, int xr, int val) {
lzytag[x] += val;
tree[x] += val * (xr - xl + 1);
}
void pushdown(int x, int xl, int xr) {
if(lzytag[x] != 0) {
int mid = (xl + xr) / 2;
addtag(ls(x), xl, mid, lzytag[x]); addtag(rs(x), mid + 1, xr, lzytag[x]);
lzytag[x] = 0;
}
}
void update(int l, int r, int x, int xl, int xr, int val) {
if (l <= xl && xr <= r) {
addtag(x, xl, xr, val);
return ;
}
pushdown(x, xl, xr);
int mid = (xl + xr) / 2;
if (l <= mid) update(l, r, ls(x), xl, mid, val);
if (mid <= r) update(l, r, rs(x), mid + 1, xr, val);
pushup(x);
}
int query(int l, int r, int x, int xl, int xr) {
if (xl >= l && r >= xr) return tree[x];
pushdown(x, xl, xr);
int res = 0;
int mid = (xl + xr) / 2;
if (l <= mid) res += query(l, r, ls(x), xl, mid);
if (mid <= r) res += query(l, r, rs(x), mid + 1, xr);
pushup(x);
return res;
}
signed main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int op;
cin >> op;
if (op == 1) {
int l, r, val;
cin >> l >> r >> val;
update(l, r, 1, 1, n, val);
} else if (op == 2) {
int l, r;
cin >> l >> r;
cout << query(l, r, 1, 1, n) << "\n";
}
}
return 0;
}
今天是植树节，一群大佬秀出了自己的数据结构，而我连线段树都不会 /kel
调过了！！！
友情提醒 qry 的时候是不用 pushup 的，因为 qry 时子结点的值刚才用父结点的标记更新，本质上没有做出改变。可以减小常数。
确实我也是这样的