数状数组/线段树 代码存档
2026-02-13 19:12:14
发布于：广东
Update: 决定把这个做成较为详细的笔记
Update: 骗你的，做不下去了，只做了树状数组
排版很乱，见谅哈。
1.树状数组（Binary Indexed Tree,BIT,二叉索引树）
简介：可以处理区间修改，查询区间和/差等问题（仅支持前缀可减的操作）。
问题：给出一个数组 ，请在 的时间复杂度内执行区间修改或区间查询操作。
关于树状数组，我们从一个很聪明的函数讲起：
指 与 按位与的结果。
可以发现，当 是奇数时，，反之 二进制下的 从左往右出现的最后一个 及其后面的 组成的数的十进制。这么听着有点绕，例如 ， 取 ，得 ，所以 。当然这个只是铺垫后面的内容，听不懂也没关系。你只需要知道 的值一定是 的幂次，前提 。
关键在于我们按 的值将每个数分层并连边，居然神奇的出现了一棵二叉树！（如下图）
这棵二叉树非常神奇，对于节点 ，如果他是左子结点，他的父节点为 ，否则他的父节点为 。因此我们可以利用 ，对区间段进行前缀和计算。
构造一个辅助数组 ，定义 为覆盖节点 及其左子树的区间和，即：
这时我们回归问题。
修改
观察 的定义，修改一个节点的值，只需要同步修改在其右上方的祖先的值即可。
查询
只需要将所有其左上方的祖先及其本身的值即可。
void add(int x,int d){//修改，将x+d
while(x<=n){
c[x]+=d;
x+=lowbit(x);
}
}
int query(int x){//查询x的值
int sum = 0;
while(x>0){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
对于区间修改问题，由于 本质上是前缀和，所以差分一下即可（换句话说，区间修改问题必须有可差分性）
模板题，上模板。
例题：
提醒各位初学者，本题虽然不必离散化，但是你拿 建的树状数组就需要注意阈值上限是 不是 了。可能你们会觉得这句话很糖。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[500009],c[500009];
int lowbit(int x){return x&-x;}
void add(int x,int d){
while(x<=500000){
c[x]+=d;
x+=lowbit(x);
}
}
int query(int x){
int ans = 0;
while(x>0){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int ans;
int t[500009];
signed main(){
cin>>n;
for(int i = 1;i<=n;++i){
cin>>a[i];
}
for(int i = 1;i<=n;++i){
ans+=query(a[i]-1);
add(a[i],1);
}
cout<<ans;
}
由于 达到了 ，我们无法直接按照 的值建树状数组，因此考虑离散化：
- 1.复制 数组存入 ，将 排序。
- 2.将 用 函数去重。
- 3.用二分找原 在 中的位置。
这样我们就得到了 的相对大小顺序，把值域缩到了 之内，可以建树状数组了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[500009],t[500009],c[500009];
int lowbit(int x){return x&-x;}
void add(int x,int d){
while(x<=n){
c[x]+=d;
x+=lowbit(x);
}
}
int query(int x){
int sum = 0;
while(x>0){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
signed main(){
cin>>n;
for(int i = 1;i<=n;++i){
cin>>a[i];
t[i] = a[i];//离散化-复制
}
sort(t+1,t+n+1);//离散化-排序
int len = unique(t+1,t+n+1)-t-1;//离散化-去重
for(int i = 1;i<=n;++i){
a[i] = lower_bound(t+1,t+len+1,a[i])-t;//离散化-二分对应原数组，找相对位置
}
int ans = 0;
for(int i = n;i>=1;--i){
ans+=query(a[i]-1);
add(a[i],1);
}
cout<<ans;
}
2.线段树/(lazy_tag)
没写完。
3.权值线段树
洛谷我没找到板（没有给权值线段树の标签），自己放一个草题。
题目描述
给出 ，约定 。对于 ：
求出 。
输入
给出
输出
输入
6
5 1 2 5 4 6
输出
5
4
1
0
1
1
无需离散化&动态开点
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc 2*i
#define rc lc+1
#define N 10000001
int tr[40000009];
void pushup(int i){
tr[i] = tr[lc]+tr[rc];
}
void update(int i,int l,int r,int x,int d){//x出现个数+d
int mid = l+r>>1;
if(l == r){
tr[i]+=d;
return ;
}
if(x<=mid){
update(lc,l,mid,x,d);
}else update(rc,mid+1,r,x,d);
pushup(i);
}
int query_x_cnt(int i,int l,int r,int x){//查询x出现了多少次
int mid = l+r>>1;
if(l == r) return tr[i];
if(x<=mid){
return query_x_cnt(lc,l,mid,x);
}else return query_x_cnt(rc,mid+1,r,x);
}
int query_xy_cnt(int i,int l,int r,int ql,int qr){//查询[ql,qr]内元素个数
if(ql>r||qr<l) return 0;
if(ql<=l&&r<=qr) return tr[i];
int mid = l+r>>1;
return query_xy_cnt(lc,l,mid,ql,qr)+query_xy_cnt(rc,mid+1,r,ql,qr);
}
int kth(int i,int l,int r,int k){//第k小
if(l == r) return l;
int mid = l+r>>1;
if(k<=tr[lc]){
return kth(lc,l,mid,k);
}else return kth(rc,mid+1,r,k-tr[lc]);
}
int findpre(int x){//找x前驱
int k = query_xy_cnt(1,1,N,1,x-1);
if(k) return kth(1,1,N,k);
return -1;
}
int findnext(int x,int n){//找x后继
int k = query_xy_cnt(1,1,N,1,x)+1;
if(k == n)return -1;
return kth(1,1,N,k);
}
int n,x;
signed main(){
cin>>n>>x;
cout<<x<<'\n';
update(1,1,N,x,1);
for(int i = 2;i<=n;++i){
cin>>x;
int ans = 0;
if(query_x_cnt(1,1,N,x) == 0){
int pre = findpre(x);
int nxt = findnext(x,i);
if(pre == -1){
ans = nxt-x;
}else if(nxt == -1){
ans = x-pre;
}else ans = min(nxt-x,x-pre);
}
cout<<ans<<'\n';
update(1,1,N,x,1);
}
}
九转大肠有没有食欲
发现与区间和有关，套上前缀和 。
考虑列不等式 ，直接维护这个是 的肯定不现实。
考虑变换得 ，考虑枚举 ，那么我们只要找出满足条件的 的数量，就是对于 的选择。
于是我们使用权值线段树维护 的值，也就是要计算的 ，那把小于 的 全部丢进权值线段树即可。
需要注意的是，本题阈值很大，记得动态开点处理。
#include<bits/stdc++.h>
using namespace std;
#define int long long
// #define lc 2*i
// #define rc lc+1
struct node{
int lc,rc,sum;
};
node tr[40000009];
int tot;
void pushup(int i){
tr[i].sum = tr[tr[i].lc].sum+tr[tr[i].rc].sum;
}
void update(int i,int l,int r,int x,int d){//x出现个数+d
int mid = l+r>>1;
if(l == r){
tr[i].sum+=d;
return ;
}
if(x<=mid){
if(tr[i].lc == 0) tr[i].lc = ++tot;
update(tr[i].lc,l,mid,x,d);
}else{
if(tr[i].rc == 0) tr[i].rc = ++tot;
update(tr[i].rc,mid+1,r,x,d);
}
pushup(i);
}
int query_xy_cnt(int i,int l,int r,int ql,int qr){//查询[ql,qr]内元素个数
if(i == 0) return 0;
if(ql>r||qr<l) return 0;
if(ql<=l&&r<=qr) return tr[i].sum;
int mid = l+r>>1;
int sum = 0;
if(ql<=mid) sum+=query_xy_cnt(tr[i].lc,l,mid,ql,qr);
if(qr>mid) sum+=query_xy_cnt(tr[i].rc,mid+1,r,ql,qr);
return sum;
}
int l = -1e10,r = 1e10;
int n,a[100009],sum[100009],ll,rr;
signed main(){
cin>>n>>ll>>rr;
for(int i = 1;i<=n;++i){
cin>>a[i];
sum[i] = sum[i-1]+a[i];
}
tr[tot].lc = tr[tot].rc = tr[tot].sum = 0;
++tot;
update(1,l,r,0,1);
int ans = 0;
for(int i = 1;i<=n;++i){
ans+=query_xy_cnt(1,l,r,sum[i]-rr,sum[i]-ll);
update(1,l,r,sum[i],1);
}
cout<<ans;
}
全部评论 121
建议补充lowbit的原理：
其次，为什么 可以到数字 的二进制表示中最低位的 所对应的十进制数值？这个就比较暴力了，由于计算机中负数是补码存储：
-x = ~x + 1。~x会把 二进制全部取反，加 会让从最低位 开始往后全部变回 、最低位 恢复成 ，再与原数 ，只会保留最低位的 1，其余全变 ，如果还没有理解的话画一张图应该就好了。(o゜▽゜)o☆1周前 来自 重庆
1
有帮助，赞一个