数状数组/线段树代码存档

Zzzzzzsr（不处）

2026-02-01 15:49:42

发布于：广东

44阅读

0回复

0点赞

Update: 决定把这个做成较为详细的笔记

Update: 骗你的，做不下去了，只做了树状数组

排版很乱，见谅哈。

1.树状数组（Binary Indexed Tree,BIT,二叉索引树）

简介：可以处理区间修改，查询区间和/差等问题（仅支持前缀可减的操作）。

问题：给出一个数组 $\{a_n\}$ ，请在 $\log{n}$ 的时间复杂度内执行区间修改或区间查询操作。

关于树状数组，我们从一个很聪明的函数讲起：

$\tt{lowbit(x)=x\&(-x)}$

指 $x$ 与 $-x$ 按位与的结果。

可以发现，当 $x$ 是奇数时， $\tt{lowbit(x)=1}$ ，反之 $\tt{lowbit(x)}=$ 二进制下的 $x$ 从左往右出现的最后一个 $1$ 及其后面的 $0$ 组成的数的十进制。这么听着有点绕，例如 $\tt{lowbit(6)}$ ， $(6)_{10}=(110)_2,$ 取 $10$ ，得 $(10)_2=2$ ，所以 $\tt{lowbit(6)=2}$ 。当然这个只是铺垫后面的内容，听不懂也没关系。你只需要知道 $\tt{lowbit(x)}$ 的值一定是 $2$ 的幂次，前提 $x\ne 0$ 。

关键在于我们按 $\tt{lowbit(x)}$ 的值将每个数分层并连边，居然神奇的出现了一棵二叉树！（如下图）

这棵二叉树非常神奇，对于节点 $i$ ，如果他是左子结点，他的父节点为 $\tt{i+lowbit(i)}$ ，否则他的父节点为 $\tt{i-lowbit(i)}$ 。因此我们可以利用 $\tt{lowbit}$ ，对区间段进行前缀和计算。

构造一个辅助数组 $c[]$ ，定义 $c_i$ 为覆盖节点 $i$ 及其左子树的区间和，即：

$c_i=\sum_{i-lowbit(i)+1}^i a_i$

这时我们回归问题。

修改

观察 $c_i$ 的定义，修改一个节点的值，只需要同步修改在其右上方的祖先的值即可。

查询

只需要将所有其左上方的祖先及其本身的值即可。

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;
}

对于区间修改问题，由于 $\tt{query}$ 本质上是前缀和，所以差分一下即可（换句话说，区间修改问题必须有可差分性）

模板题，上模板。

例题：

股票

提醒各位初学者，本题虽然不必离散化，但是你拿 $a_i$ 建的树状数组就需要注意阈值上限是 $\max a_i$ 不是 $n$ 了。可能你们会觉得这句话很糖。

#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;
}

逆序对

由于 $a_i$ 达到了 $10^9$ ，我们无法直接按照 $a_i$ 的值建树状数组，因此考虑离散化：

1.复制 $a$ 数组存入 $t$ ，将 $t$ 排序。
2.将 $t$ 用 $\tt{unique}$ 函数去重。
3.用二分找原 $a_i$ 在 $t$ 中的位置。

这样我们就得到了 $a_i$ 的相对大小顺序，把值域缩到了 $5\times 10^5$ 之内，可以建树状数组了。

#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.权值线段树

洛谷我没找到板（没有给权值线段树の标签），自己放一个草题。

题目描述

给出 $n,\{a_n\}$ ，约定 $b_1=a_1$ 。对于 $2\le i \le n$ ：

$b_i=\min_{j=1}^{i-1}|a_j-a_i|$

求出 $\{b_n\}$ 。

输入

给出 $n,\{a_n\}$

输出

$\{b_n\}$

输入 $1$

6
5 1 2 5 4 6

输出 $1$

$1\le n \le 10^5,1\le a_i\le 10^7$ 无需离散化&动态开点

$\tt{Code:}$

#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);
    }
}

回转寿司,luogu5459,绿

~~九转大肠有没有食欲~~

发现与区间和有关，套上前缀和 $sum$ 。

考虑列不等式 $L\le sum_r-sum_{l-1}\le R$ ，直接维护这个是 $n^2$ 的肯定不现实。

考虑变换得 $sum_r-R\le sum_l-1\le sum_r-L(l<i)$ ，考虑枚举 $sum_i$ ，那么我们只要找出满足条件的 $sum_{l-1}$ 的数量，就是对于 $sum_i$ 的选择。

于是我们使用权值线段树维护 $sum$ 的值，也就是要计算的 $[sum_i-R,sum_i-L]$ ，那把小于 $i$ 的 $sum_j$ 全部丢进权值线段树即可。

需要注意的是，本题阈值很大，记得动态开点处理。

#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;
}

有帮助，赞一个

去预览

0/2000

全部评论 13

妈妈说名字太长会有不太聪明的人读
👍👍

1小时前来自广东
0
Xylophone
关于BIT2评级比BIT1低这件事

1小时前来自广东
0
Xylophone
我要zkw线段树我要zkw线段树Xyl以卡常为食就要zkw就要zkw卡常卡常我要zkw谁来给我zkw线段树就要zkw不要大递归不要不要

1小时前来自广东
0
- cjdst
  回复
  Xylophone
  不要再卡常了，休息一下吧（
  
  1小时前来自广东
  0
- Xylophone
  回复
  cjdst
  总有刁民想害朕（
  
  1小时前来自广东
  0
- Xylophone
  回复
  cjdst
  zkw还没学会（）b站上某UP说自己现在只写zkw和动态开点给我看红温了你们知道吗
  
  1小时前来自广东
  0
Gragher
不如我儿子 @Lyzc0dr 的 https://www.acgo.cn/discuss/rest/58654

20小时前来自浙江
0
- Gragher
  回复
  Gragher
  
  20小时前来自浙江
  0
- Zzzzzzsr（不处）
  回复
  Gragher
  好吧这个确实写的比我好多了没关系我是gay这篇文章我主讲题目解法哈哈哈我要去路了
  
  20小时前来自广东
  0
Gragher
我算是看懂了，你和sbtrq讲的就不是一个东西，他是按照c去建树的（正常人他妈都这么建的吧，我还特地去查了OIWiki，深入浅出，算法竞赛），你这个是按照lowbit分层去建的，实际上最终计算的都是c，所以效果是一样的

20小时前来自浙江
0
- Gragher
  回复
  Gragher
  （但你这画法着实诡异
  
  20小时前来自浙江
  0
- Zzzzzzsr（不处）
  回复
  Gragher
  难道只有我们校编的书这么建
  
  20小时前来自广东
  0
- Ymh
  回复
  Gragher
  对呀，我们学校就是这个图
  
  20小时前来自广东
  0
cjdst
树状数组是你这么画的吗

22小时前来自广东
0
- cjdst
  回复
  cjdst
  不是长这样吗
  
  22小时前来自广东
  0
- Zzzzzzsr（不处）
  回复
  cjdst
  这几把什么（一种植物）图
  
  22小时前来自广东
  0
- cjdst
  回复
  Zzzzzzsr（不处）
  你把 $i\rarr i+\text{lowbit}(i)$ 连一下就知道了
  
  22小时前来自广东
  0
好好
1

23小时前来自四川
0
好好
1

23小时前来自四川
0
好好
1

23小时前来自四川
0
yanghongzheng
%%%

昨天来自北京
0
cjdst
主包快学动态开点和线段树合并

昨天来自广东
0
Ymh
ddddddddddddddddddd

昨天来自广东
0
Zzzzzzsr（不处）
d

昨天来自广东
0