P3368 【模板】树状数组 2
2023-09-27 14:28:12 时间
\(P3368\) 【模板】树状数组 \(2\)
- 知识点:区间修改,单点查询
通过 差分(就是记录数组中每个元素与前一个元素的差),可以把这个问题转化为问题 单点修改,区间查询
查询
设原数组为\(a[i]\), 设数组\(b[i]=a[i]-a[i-1](a[0]=0)\),则\(\displaystyle a[i]=\sum_{j=1}^{i}b[j]\),可以通过求\(b[i]\)的前缀和查询。
修改
当给区间\([l,r]\)加上\(x\)的时候,\(a[l]\)与前一个元素 \(a[l-1]\)的差增加了\(x\),\(a[r+1]\)与 \(a[r]\)的差减少了\(x\)。根据\(b[i]\)数组的定义,只需给\(a[l]\)加上\(x\), 给 \(a[r+1]\)减去\(x\)即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int a[N]; // a是原数组。t是差分数组,用树状数组维护
int n, m;
//树状数组模板
int tr[N];
int lowbit(int x) {
return x & -x;
}
void add(int x, int c) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int sum(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main() {
scanf("%d %d", &n, &m);
//原数组
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int op, l, r, v, k;
while (m--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d %d %d", &l, &r, &v);
add(l, v), add(r + 1, -v);
} else {
scanf("%d", &k);
//树状数组维护的是变化量,还需要加上原来的值
printf("%d\n", a[k] + sum(k)); //求某点的值
}
}
return 0;
}
相关文章
- 工具--按指定的word模板, 将MySQL数据库表信息导出生成word文档
- C#使用Aspose.Words操作word文档(利用模板2)
- 【VSCode】配置vue快捷键/快速输入/模板
- 【ChatGPT模板】教学辅助教案篇
- PowerDesigner如何自定义报表模板
- 408 | 数据结构代码算法题模板技巧 之 顺序表(数组)
- 为 Blade 模板引擎添加新文件扩展名
- Web网站模板-健身房宣传响应式网站模板(HTML+CSS+JavaScript)
- 浅析setup如何通过ref获取子组件实例中的DOM结构/数据/方法及获取子组件实例数据都是空的处理(defineExpose API 的使用)、Vue3模板引用refs、在组合式API中使用template refs、for循环中如何获取及重置refs、如何监听模板引用
- 设计模式-模板方法模式
- 洛谷 P4779 【模板】单源最短路径(标准版)
- SpringBoot+Poi-tl根据Word模板动态生成word(含动态行表格、合并单元格)
- C++模板中的静态
- CRF++模板使用(转)
- 16行为型模式之模板模式