生成一个可支持插入、查询、修改、删除的线段树
时间: 2023-09-30 14:10:58 浏览: 36
以下是一个基本的线段树模板,可以支持插入、查询、修改和删除操作:
```C++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct Node {
int l, r;
int sum;
} tree[MAXN * 4];
int a[MAXN];
void build(int p, int l, int r) {
tree[p].l = l;
tree[p].r = r;
if (l == r) {
tree[p].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}
void update(int p, int x, int v) {
if (tree[p].l == tree[p].r) {
tree[p].sum += v;
return;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) update(p << 1, x, v);
else update(p << 1 | 1, x, v);
tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}
int query(int p, int l, int r) {
if (tree[p].l >= l && tree[p].r <= r) return tree[p].sum;
int mid = (tree[p].l + tree[p].r) >> 1;
int res = 0;
if (l <= mid) res += query(p << 1, l, r);
if (r > mid) res += query(p << 1 | 1, l, r);
return res;
}
void remove(int p, int x) {
if (tree[p].l == tree[p].r) {
tree[p].sum = 0;
return;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) remove(p << 1, x);
else remove(p << 1 | 1, x);
tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
while (true) {
int op, x, y;
cin >> op;
if (op == 1) {
cin >> x >> y;
update(1, x, y);
} else if (op == 2) {
cin >> x >> y;
cout << query(1, x, y) << endl;
} else if (op == 3) {
cin >> x >> y;
remove(1, x);
a[x] = y;
update(1, x, y);
} else if (op == 4) {
break;
}
}
return 0;
}
```
在这个模板中,结构体 `Node` 表示线段树的节点,`l` 表示节点所代表的区间的左端点,`r` 表示节点所代表的区间的右端点,`sum` 表示节点所代表的区间的和。数组 `tree` 用于存储线段树。
函数 `build()` 用于构建线段树,`update()` 用于修改某个位置的值,`query()` 用于查询某个区间的和,`remove()` 用于删除某个位置的值。在主函数中,通过输入不同的操作来实现对线段树的操作。