树状数组相关 - “山头斜照却相迎”
2026-07-13 19:56:35
发布于：浙江
模板：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,s[N];//原数组，树状数组
int lowbit(int x){
return x&(-x);
}
void add(int x,int k){
for(int i=x;i<=n;i+=lowbit(i))s[i]+=k;
return;
}
int h(int x){
int ans=0;
for(int i=x;i>=1;i-=lowbit(i)){
ans+=s[i];
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
add(i,x);
}
for(int i=1;i<=m;i++){
int z;
cin>>z;
if(z==1){
int x,k;
//将第x个数加上k
cin>>x>>k;
add(x,k);
}else{
int x,y;
cin>>x>>y;
//求出[x,y]内每个数的和
cout<<h(y)-h(x-1)<<'\n';
}
}
return 0;
}
比较重要的几个部分：
1.lowbit函数
int lowbit(int x){
return x&(-x);
}
寻找x这个数的二进制数状态下从右往左的第一个1
关于树状数组：
树状数组一般用来维护前缀值（这个数值可以很多样）。表示从i到i-lowbit(i)+1（长度为lowbit）的区间中符合要求的数（也就是前缀数值）。
应该可以这样理解。
2.add函数
void add(int x,int k){
for(int i=x;i<=n;i+=lowbit(i))s[i]+=k;
return;
}
这个函数用来单点修改（包括从一开始不是有个初始值吗，那些个数不用去专门考虑怎么处理，直接当作从零开始单点修改就行）。
单点修改不但需要修改自己，还需要把包含了自己的那些个一并修改掉。
关于为什么是加lowbit(i):
第一个包含x[i]本身的肯定是a[i]，而我们要找的是i之后第一个包含a[i]的a[x]。
而这个所谓的a[x]，它的区间覆盖范围是：x-lowbit(x)+1 - x
现在遍历到i嘛，让i+lowbit(i)，就是让i的最后一位一往前挪了一位，变成了现在的x。
那么：x-lowbit(x)-1 - x 肯定能够包含现在的这个i
另外呢。线段树，分块，树状数组它们是有一点点互相包含的意味在的。
运用范围如此划定：分块运用范围>线段树>树状数组
在线段树1题面和树状数组1题面完全相同的情况下。
我们可以对它们的实现方法分别做一个分析：
相同点：
1.同样都是树形结构（类似），时间复杂度基本都是
2.都是将问题拆分成段来解决（先将问题拆分成小段，在小段上操作，最后拼出大段）
其他：
关于线段树，它主要是用树懒标记的下放和回收完成了这些操作。
而树状数组，它的加操作现在单点进行修改，然后再根据lowbit去传到包含自己的区间。
query求和，则是将1-now分解成：S[now-lowbit(now)+1 - now]+S[[now-lowbit(now)+1-lowbit([now-lowbit(now)+1)+1 - [now-lowbit(now)+1]+······
树状数组2
唔。刚好全反过来。
区间修改+单点查询。
这很快就能让人想到差分。
用树状数组维护差分数组，再到差分数组上去做前缀和。
就是一些细节比较需要注意。
逆序对
如果用线段树来完成逆序对，那么就应该用权值线段树。
那如果用树状数组来完成线段树呢？
逆序对：i<j且a[i]>a[j]
用树状数组去维护每个数字出现的次数。
注意需要离散化。
树状数组就是维护前缀的喵。
树状数组的大部分运用其实线段树都能做到。
它唯一的优点有两个：
1.码量小（这就代表着调试容易，速度快）
2.时间复杂度常数小（其实这跟码量也是挂钩的）
树状数组较为经典的运用有两个：
1.树状数组求逆序对
2.树状数组二分
另外，补充一点：树状数组求逆序对的变式：星星
大概就是给出两个下表（xy）然后问，每一个点（假设当前点的下表是x[i]y[i]）询问多少个别的点，x坐标小于等于x[i]且y坐标小于等于y[i]
看似（好像）需要二位前缀和。
实际上，我们可以先将一维排序。
另一维使用逆序对的做法去看有多少个小于它的。
它的代码有一点时需要注意的：
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+4;
struct Node{
int x,y;
}node[N];
bool cmp(Node a,Node b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
int n,w[N];//树状数组
int lowbit(int x){
return x&(-x);
}
void add(int pos,int whi){
for(int i=pos;i<=N-1;i+=lowbit(i))w[i]+=whi;
return;
}
int c[N];//存储星星等级
int q(int x){
int sum=0;
for(int i=x;i>=1;i-=lowbit(i))sum+=w[i];
return sum;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>node[i].x>>node[i].y;
for(int i=1;i<=n;i++)node[i].y++;
sort(node+1,node+1+n,cmp);
for(int i=1;i<=n;i++){
c[q(node[i].y)]++;
add(node[i].y,1);
}
for(int i=0;i<n;i++)cout<<c[i]<<"\n";
return 0;
}
注意到排序这边：我将y设为了第二关键字。
为什么？
因为星星的价位计算是“小于等于”而不是“小于”。
也就是说，当x相等。
y1<y2，那么y1会对y2做出贡献。
那么当y2排在y1的前面，贡献计算就会错误。
所以需要设置第二关键字。
另外就是注意到：add()函数中的for循环，i<=N-1而不是i<=n。
因为树状数组是以星系坐标为下标的。
而不是以星星个数为下标的。
来看看二分。
树状数组二分就是利用它的二进制构造和倍增思想去在时间复杂度内找到你想找的数。
随机插入一道树状数组变式题。
https://www.luogu.com.cn/problem/P1972
HH的项链
树状数组维护的是当前数字是不是当前第一个出现的（从左往右遍历，目前遍历到的就是第一个，前面遍历到的都不再算数）。
如果是w[i]=1,w[i]=0（因为只有第一个是有价值的）
将询问以r为排序依据升序排列。
从1到n遍历ri，使用一个lst数组去维护上一个出现的相同数的位置，将目前便利到的+1，将上一个 -1。
然后判断有没有询问的r与目前遍历到的ri相同。
计算一下从l到r“有价值出现”的数字的个数。前缀和相加即可。
所以本质上还是前缀嘛。
只是变得比较高级。
再去练一道https://www.luogu.com.cn/problem/P5677
配对统计
这道题是我第一道自主思考了十多分钟的树状数组题目。
写一下想到了什么：
1.因为也是区间询问，所以我联系项链那题，想了要不要排序
2.我将绝对值的思路转变，不磕公式，想到了它的涵义：即，a[x]与a[y]之间的距离（差值）需要是整个数组中，a[x]与其他a[i]配对相比，最近的
3.思考了应该用线段树维护什么
好了，现在来看差了什么：
1.如何想到树状数组：区间查询，1e5左右的n，很容易想到线段树和树状数组。
2.如何找到所有配对（并且分析复杂度）
这里空空如也
有帮助，赞一个