【数据结构】线段树算法总结（区间修改）

知识概览

线段树一般有5个操作：

pushup：用子节点更新当前节点信息
pushdown：把懒标记往下传
build：初始化一棵树
modify：修改一个区间
query：查询一个区间

不带懒标记（支持单点修改）的线段树算法见本人博客：

【数据结构】线段树算法总结（单点修改）-CSDN博客文章浏览阅读81次，点赞2次，收藏3次。【代码总结】线段树算法总结（单点修改）https://blog.csdn.net/u012181348/article/details/135119627?spm=1001.2014.3001.5501

例题展示

题目链接

243. 一个简单的整数问题2 - AcWing题库https://www.acwing.com/problem/content/244/

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int n, m;
int w[N];
struct Node
{int l, r;LL sum, add;
} tr[N * 4];void pushup(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void pushdown(int u)
{auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];if (root.add){left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;root.add = 0;}
}void build(int u, int l, int r)
{if (l == r) tr[u] = {l, r, w[r], 0};else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}void modify(int u, int l, int r, int d)
{if (tr[u].l >= l && tr[u].r <= r){tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;tr[u].add += d;}else    // 一定要分裂{pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) modify(u << 1, l, r, d);if (r > mid) modify(u << 1 | 1, l, r, d);pushup(u);}
}LL query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL sum = 0;if (l <= mid) sum = query(u << 1, l, r);if (r > mid) sum += query(u << 1 | 1, l, r);return sum;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &w[i]);build(1, 1, n);char op[2];int l, r, d;while (m--){scanf("%s%d%d", op, &l, &r);if (*op == 'C'){scanf("%d", &d);modify(1, l, r, d);}else printf("%lld\n", query(1, l, r));}return 0;
}