用C写一个线段树模板代码
时间: 2024-01-29 12:02:34 浏览: 27
以下是一个基本的线段树模板代码,其中实现了区间求和和区间修改操作。
```
#include <cstdio>
#include <cstring>
const int MAXN = 100000;
int n, m; // 线段树区间长度和操作个数
int a[MAXN + 5]; // 原始数组
int sum[MAXN * 4 + 5]; // 线段树节点保存的区间和
int add[MAXN * 4 + 5]; // 线段树节点保存的懒标记
// 更新操作
void pushup(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
// 下传懒标记
void pushdown(int rt, int ln, int rn) {
if (add[rt]) {
add[rt << 1] += add[rt];
add[rt << 1 | 1] += add[rt];
sum[rt << 1] += add[rt] * ln; // 左子节点区间长度为 ln
sum[rt << 1 | 1] += add[rt] * rn; // 右子节点区间长度为 rn
add[rt] = 0;
}
}
// 建树操作
void build(int l, int r, int rt) {
if (l == r) {
sum[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushup(rt);
}
// 区间修改操作
void update(int L, int R, int c, int l, int r, int rt) {
if (L <= l && r <= R) {
add[rt] += c;
sum[rt] += c * (r - l + 1);
return;
}
int mid = (l + r) >> 1;
pushdown(rt, mid - l + 1, r - mid); // 下传懒标记
if (L <= mid) update(L, R, c, l, mid, rt << 1);
if (R > mid) update(L, R, c, mid + 1, r, rt << 1 | 1);
pushup(rt);
}
// 区间查询操作
int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return sum[rt];
int mid = (l + r) >> 1;
pushdown(rt, mid - l + 1, r - mid); // 下传懒标记
int ans = 0;
if (L <= mid) ans += query(L, R, l, mid, rt << 1);
if (R > mid) ans += query(L, R, mid + 1, r, rt << 1 | 1);
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, n, 1);
for (int i = 1; i <= m; i++) {
int op, l, r, c;
scanf("%d", &op);
if (op == 1) {
scanf("%d%d%d", &l, &r, &c);
update(l, r, c, 1, n, 1);
} else {
scanf("%d%d", &l, &r);
printf("%d\n", query(l, r, 1, n, 1));
}
}
return 0;
}
```