树状数组简介
前置知识：lowbit
lowbit是指一个数最低位的 \(1\)
- \(4=(100)_2\) -> \(lowbit(100)=(100)_2=4\) 即 \(lowbit(4)=4\)
- \(6=(110)_2\) -> \(lowbit(110)=(10)_2=2\) 即 \(lowbit(6)=2\)
- \(7=(111)_2\) -> \(lowbit(111)=(1)_2=1\) 即 \(lowbit(7)=1\)
树状数组
树状数组是一个可以快速处理前缀信息的数据结构
树状数组一般使用数组进行存储，数组中 \(x\) 号节点，存储的是区间 \([x−lowbit(x)+1,x]\) 的信息和，利用这
一点可以在线性时间内建出树状数组），也可以实现全局的第 \(k\) 小查询，其中 \(tree[x]\) 表示 \(\sum_{{i=x-lownit(x)+1}}^x a_i\)
树状数组特性：
- 每个内部节点 \(tree[x]\) 保存以它为根的所有叶子节点的和
- 每个内部节点 \(tree[x]\) 的子节点数等于 \(lowbit(x)\) 的位数
- 每个内部节点 \(tree[x]\) 的父节点是 \(tree[x+lowbit(x)]\)
- 树的深度为 \(logn\)
树状数组实现
1.建树
直接用加点函数循环
int add(int x,int y){
while(x<=n){
t[x]+=y;//此节点赋值，所有祖先节点都增加（与前缀和一样）
x+=x&-x;//与x=x+lowbit(x)等价
}
}
调用入口：
for(int i=1;i<=n;i++){//点得一个一个加
cin>>a[i];
add(i,a[i]);
}
2.单点修改
修改函数与上面建树函数相同
我们如果更改点 \(1\) ，需要更改的节点如图红圈部分：
int add(int x,int y){
while(x<=n){
t[x]+=y;//此节点同所有祖先节点都增加
x+=x&-x;//与x=x+lowbit(x)等价
}
}
调用入口：add(x,a);
3.查询
我们如果查询区间 \([4,7]\) ，先求出区间 \([1,7]\) (红色线段表示)和区间 \([1,3]\) (蓝色线段表示)再相减（绿色线段表示），需要计算的节点如图红圈（ 区间 \([1,7]\) 需要计算的节点）及蓝圈（ 区间 \([1,3]\) 需要计算的节点）部分：
int ask(int x){
int val=0;
while(x>0){
val+=t[x];//求出1-x的值
x-=x&-x;//与x=x-lowbit(x)等价
}
return val;//返回答案
}
调用入口：ask(r)-ask(l-1);
单点查询要借助区间查询，如果信息支持区间差的话，可以用 \([1, y]\) 的值减去 \([1, y − 1]\) 的值
int ask(int x){
int val=0;
while(x>0){
val+=t[x];//求出1-x的值
x-=x&-x;//与x=x-lowbit(x)等价
}
return val;//返回答案
}
调用入口：ask(x)-ask(x-1);
4.区间修改
区间修改得更改很多地方
建树
int add(int x,int y){
while(x<=n){
t[x]+=y;//此节点赋值，所有祖先节点都增加（与前缀和一样）
x+=x&-x;//与x=x+lowbit(x)等价
}
}
调用入口：
for(int i=1;i<=n;i++){//点得一个一个加
cin>>a[i];
add(i,a[i]-a[i-1]);
}
修改
int add(int x,int y){
while(x<=n){
t[x]+=y;//此节点同所有祖先节点都增加
x+=x&-x;//与x=x+lowbit(x)等价
}
}
调用入口：
add(l,k);
add(r+1,-k);
如果修改单点则把 \(l,r\) 都赋值为 \(x\)
单点查询
调用入口变为：ask(x)
区间查询
\[这个人颓废去了，N年后再更 \]树状数组到这就结束了，练习一下吧！
例题1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
-
将某一个数加上 \(x\)
-
求出某区间每一个数的和
输入格式
第一行包含两个正整数 \(n,m\)，分别表示该数列数字的个数和操作的总个数。 第二行包含 \(n\) 个用空格分隔的整数，其中第 \(i\)
个数字表示数列第 \(i\) 项的初始值。
接下来 \(m\) 行每行包含 \(3\) 个整数，表示一个操作，具体如下：
-
1 x k含义：将第 \(x\) 个数加上 \(k\) -
2 x y含义：输出区间 \([x,y]\) 内每个数的和
输出格式
输出包含若干行整数，即为所有操作 \(2\) 的结果。
样例#1
输入
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出
14
16
提示
对于 \(30\%\) 的数据，\(1 \le n \le 8\)，\(1\le m \le 10\)；
对于 \(70\%\) 的数据，\(1\le n,m \le 10^4\)；
对于 \(100\%\) 的数据，\(1\le n,m \le 5\times 10^5\)。
code
这题可以用用树状数组单点修改，区间查询来做
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int t[500001],a[500001],n,m;
int add(int x,int y){
while(x<=n){
t[x]+=y;//此节点同所有祖先节点都增加
x+=x&-x;//与x=x+lowbit(x)等价
}
}
int ask(int x){
int val=0;
while(x>0){
val+=t[x];//求出1-x的值
x-=x&-x;//与x=x-lowbit(x)等价
}
return val;//返回答案
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){//点得一个一个加
cin>>a[i];
add(i,a[i]);
}
for(int i=1;i<=m;i++){
int flag,x,y;
cin>>flag>>x>>y;
if(flag==1){
add(x,y);//增加y
}else{
cout<<ask(y)-ask(x-1)<<endl;//输出区间[x,y]的值
}
}
return 0;
}
例题2
题目描述
如题，已知一个数列，你需要进行下面两种操作：
-
将某区间每一个数加上 \(x\)；
-
求出某一个数的值。
输入格式
第一行包含两个整数 \(N\)、\(M\)，分别表示该数列数字的个数和操作的总个数。
第二行包含 \(N\) 个用空格分隔的整数，其中第 \(i\) 个数字表示数列第 $i $ 项的初始值。
接下来 \(M\) 行每行包含 \(2\) 或 \(4\)个整数，表示一个操作，具体如下：
操作 \(1\)： 格式：1 x y k 含义：将区间 \([x,y]\) 内每个数加上 \(k\)；
操作 \(2\)： 格式：2 x 含义：输出第 \(x\) 个数的值。
输出格式
输出包含若干行整数，即为所有操作 \(2\) 的结果。
样例 #1
输入
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
输出
6
10
提示
对于 \(30\%\) 的数据：\(N\le8\)，\(M\le10\)；
对于 \(70\%\) 的数据：\(N\le 10000\)，\(M\le10000\)；
对于 \(100\%\) 的数据：\(1 \leq N, M\le 500000\)，\(1 \leq x, y \leq n\)，保证任意时刻序列中任意元素的绝对值都不大于 \(2^{30}\)。
code
这题可以用用树状数组区间修改，单点查询来做
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int t[500001],a[500001],n,m;
int add(int x,int y){
while(x<=n){
t[x]+=y;//此节点同所有祖先节点都增加
x+=x&-x;//与x=x+lowbit(x)等价
}
}
int ask(int x){
int val=0;
while(x>0){
val+=t[x];//求出1-x的值
x-=x&-x;//与x=x-lowbit(x)等价
}
return val;//返回答案
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){//点得一个一个加
cin>>a[i];
add(i,a[i]-a[i-1]);
}
for(int i=1;i<=m;i++){
int flag,x,y,k;
cin>>flag>>x;
if(flag==1){
cin>>y>>k;
add(x,k);
add(y+1,-k);//区间增加y
}else{
cout<<ask(x)<<endl;//输出点x的值
}
}
return 0;
}