线段树区间修改,区间查询的模板
时间: 2023-03-30 10:01:35 浏览: 118
线段树是一种常用的数据结构,用于解决区间修改和区间查询的问题。对于线段树的区间修改操作,可以采用递归的方式,将区间分为左右两个子区间,然后分别对左右子区间进行修改操作。对于线段树的区间查询操作,同样可以采用递归的方式,将区间分为左右两个子区间,然后分别对左右子区间进行查询操作,并将结果合并起来。这样就可以实现对区间修改和区间查询的高效处理。
相关问题
线段树区间修改,区间查询的代码模板
以下是线段树区间修改,区间查询的代码模板:
```c++
const int MAXN = 1e5 + 5;
int n;
int a[MAXN];
int tree[MAXN << 2];
int lazy[MAXN << 2];
void push_up(int rt) {
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
void push_down(int rt, int ln, int rn) {
if (lazy[rt]) {
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
tree[rt << 1] += lazy[rt] * ln;
tree[rt << 1 | 1] += lazy[rt] * rn;
lazy[rt] = ;
}
}
void build(int l, int r, int rt) {
if (l == r) {
tree[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
push_up(rt);
}
void update(int L, int R, int C, int l, int r, int rt) {
if (L <= l && r <= R) {
tree[rt] += C * (r - l + 1);
lazy[rt] += C;
return;
}
int mid = (l + r) >> 1;
push_down(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);
push_up(rt);
}
int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return tree[rt];
}
int mid = (l + r) >> 1;
push_down(rt, mid - l + 1, r - mid);
int sum = ;
if (L <= mid) sum += query(L, R, l, mid, rt << 1);
if (R > mid) sum += query(L, R, mid + 1, r, rt << 1 | 1);
return sum;
}
```
希望对你有所帮助!
线段树区间修改,区间查询的用结构体代码模板
以下是线段树区间修改,区间查询的用结构体代码模板:
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
struct Node {
int l, r;
int sum;
} tr[MAXN << 2];
int n, m;
int w[MAXN];
void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
if (l == r) tr[u] = {l, r, w[l]};
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 x, int c) {
if (tr[u].l == x && tr[u].r == x) tr[u].sum += c;
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, c);
else modify(u << 1 | 1, x, c);
pushup(u);
}
}
int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
else {
int mid = tr[u].l + tr[u].r >> 1;
int res = ;
if (l <= mid) res += query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
build(1, 1, n);
while (m--) {
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if (k == 1) modify(1, x, y);
else printf("%d\n", query(1, x, y));
}
return ;
}
```
以上是回答你的问题,希望对你有所帮助。
阅读全文