树状数组,Fenwick Tree
Fenwick Tree, (also known as Binary Indexed Tree,二叉索引树), is a high-performance data structure to calculate the sum of elements from the beginning to the indexed in a array.
It needs three functions and an array:
- Array sum; It stores the data of Fenwick Tree.
- int lowbit(int); To get the last 1 of the binary number. 取出最低位 1
- void modify(int, int); To modify the value of an element, the second input "val" is the value that would be added.
- int query(int); To get the sum of elements from the beginning to the indexed.
How to get the last 1 of a binary number? Use AND operating: x & (-x).
Definitions:
int sum[N]; inline int lowbit(int x) {
return x & (-x);
}
inline void modify(int x, int val) {
while (x <= n) {
d[x] += val; x += lowbit(x);
}
}
inline int query(int x) {
int sum = ;
while (x > ) {
sum += d[x]; x -= lowbit(x);
}
return sum;
}
例题1:洛谷P3374 【模板】树状数组 1
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x k 含义:将第x个数加上k
操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和
输出格式:
输出包含若干行整数,即为所有操作2的结果。
代码:
/* P3374 【模板】树状数组 1
* Au: GG
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = + ;
int n, m, d[N]; inline int lowbit(int x) {
return x & (-x);
}
inline void modify(int x, int val) {
while (x <= n) {
d[x] += val; x += lowbit(x);
}
}
inline int getsum(int x) {
int sum = ;
while (x > ) {
sum += d[x]; x -= lowbit(x);
}
return sum;
} int main() {
scanf("%d%d", &n, &m);
for (int i = , w; i <= n; i++) {
scanf("%d", &w); modify(i, w);
}
while (m--) {
int o, x, y;
scanf("%d%d%d", &o, &x, &y);
if (o == ) modify(x, y);
if (o == ) printf("%d\n", getsum(y) - getsum(x - ));
}
return ;
}
例题2:洛谷P3368 【模板】树状数组 2
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数数加上x
2.求出某一个数的和
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含2或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
操作2: 格式:2 x 含义:输出第x个数的值
输出格式:
输出包含若干行整数,即为所有操作2的结果。
数据直接 modify 到差分数组里,方便区间修改和单元素查询(原本树状数组作用是方便单元素修改和区间查询 )。
代码:
/* P3368 【模板】树状数组 2
* Au: GG
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = + ;
int n, m, d[N]; inline int lowbit(int x) {
return x & (-x);
}
inline void modify(int x, int val) {
while (x <= n) {
d[x] += val; x += lowbit(x);
}
}
inline int getsum(int x) {
int sum = ;
while (x > ) {
sum += d[x]; x -= lowbit(x);
}
return sum;
} int main() {
scanf("%d%d", &n, &m);
for (int i = , w, v = ; i <= n; i++) {
scanf("%d", &w); modify(i, w - v); v = w;
}
while (m--) {
int o, x, y, k;
scanf("%d%d", &o, &x);
if (o == ) {
scanf("%d%d", &y, &k);
modify(x, k); modify(y + , -k);
}
if (o == ) printf("%d\n", getsum(x));
}
return ;
}
最新文章
- lattice 与 modelsim 仿真 笔记
- C#删除文件和文件夹到回收站
- Cache模拟器(CacheSim)
- HtmlAgilityPack解析全国区号页面到XML
- Linux-设置环境变量
- 获得供应商最近一次报价:OVER(PARTITION BY)函数用法的实际用法
- linux 文本处理
- linux下安装filezilla客户端遇到的问题
- homework-08
- java IO类图
- python编程基础知识—列表(一)
- 各个模块的刷新js
- 错误:Java HotSpot(TM) 64-Bit Server VM warning: Insufficient space for shared memory file
- dede 采集文章内容中图片不显示的问题
- Java 集合类框架
- 心迹 使用说明&;功能展示
- Ubuntu/Linux网络配置常用命令
- 【Linux优化】Linux安装之后的优化
- CentOS 编译 GCC 7.2
- sqrt函数的实现
热门文章
- 【Vue】axios post提交请求转为form data
- Spring CGLlB动态代理
- git filter-branch
- Iconv作用以及安装问题解决
- Digital Root 的推导
- CSS深入理解line-height
- 属性选择器 [attribute^=value] [attribute~=value] [attribute|=value] [attribute*=value]
- 45-python基础-python3-字符串-常用字符串方法(三)-startswith()-endswith()
- java收藏的技术资料链接
- Python之基本的日期与时间转换 datetime、 dateutil模块