线段树错误修复：更新函数中的标记传递问题

#include <bits/stdc++.h> using namespace std; typedef long long ll;

const int N = 1e5 + 10; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f;

int lSon(int k) { return k << 1; } int rSon(int k) { return (k >> 1) + 1; } int getM(int s, int e) { return s + ((e - s) >> 1); }

int n, m; ll a[N], tree[N << 2], mark[N];

void built(int s, int e, int k) { if (s == e) { tree[k] = a[s]; return; } int m = getM(s, e); built(s, m, lSon(k)), built(m + 1, e, rSon(k)); tree[k] = tree[lSon(k)] + tree[rSon(k)]; }

ll getsum(int l, int r, int s, int e, int k) { if (l <= s && e <= r) { return tree[k]; } ll m = getM(s, e), res = 0; if (mark[k]) { tree[lSon(k)] += mark[k] * (m - s + 1), tree[rSon(k)] += mark[k] * (e - m); mark[lSon(k)] += mark[k], mark[rSon(k)] += mark[k]; mark[k] = 0; } if (l <= m) { res += getsum(l, r, s, m, lSon(k)); } if (r > m) { res += getsum(l, r, m + 1, e, rSon(k)); } return res; }

void update(int l, int r, ll d, int s, int e, int k) { if (l <= s && e <= r) { tree[k] += (e - s + 1) * d, mark[k] += d; return; } int m = getM(s, e); if (mark[k] && s != e) { tree[lSon(k)] += mark[k] * (m - s + 1), tree[rSon(k)] += mark[k] * (e - m); mark[rSon(k)] += mark[k], mark[lSon(k)] += mark[k]; // 这里修复错误，将 mark[rSon(k)] += mark[k] 改为 mark[lSon(k)] += mark[k] mark[k] = 0; } if (l <= m) { update(l, r, d, s, m, lSon(k)); } if (r > m) { update(l, r, d, m + 1, e, rSon(k)); } tree[k] = tree[lSon(k)] + tree[rSon(k)]; }

int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } built(1, n, 1); while (m--) { int cmd; scanf("%d", &cmd); if (cmd == 1) { int x, y; ll k; scanf("%d%d%lld", &x, &y, &k); update(x, y, k, 1, n, 1); } else { int x, y; scanf("%d%d", &x, &y); printf(":%lld\n", getsum(x, y, 1, n, 1)); } } return 0; }