树状数组模板题

题单链接：树状数组模板题 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

可以先看这篇文章学习或者复习一下：

【朝夕的ACM笔记】数据结构-树状数组 - 知乎 (zhihu.com)

---

P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=5e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int a[MAXN];
int t[MAXN];
//树状数组
//树状数组：数组的每个位置储存的应当是一个区间的信息
//这些区间应当包容而不相交

//单点修改
//首先修改的是单个元素
//其次修改的是包含这个元素的区间
//需要修改的区间(y,x],(x,x+lowbit(x)]------
void update(int x,int k,int n)
{
    while(x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}
//区间查询
//查询的是从[1,x]区间的和
//[1,x]=(y,x]+(y',y]+(y'',y']+------
int query(int x)
{
    int ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
//建树 O(n)建树
void build(int n)
{
    for(int i=1;i<=n;i++)
    {
        t[i]+=a[i];
        int j=i+lowbit(i);
        if(j<=n)    t[j]+=t[i];
    }
}
void solve()
{
    int n,m;    std::cin>>n>>m;
    for(int i=1;i<=n;i++)   std::cin>>a[i];
    build(n);
    for(int i=1;i<=m;i++)
    {
        int opt,x,y;    std::cin>>opt>>x>>y;
        if(opt==1)
        {
            update(x,y,n);
        }
        if(opt==2)
        {
            std::cout<<query(y)-query(x-1)<<"\n";
        }
    }
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}

P5057 [CQOI2006] 简单题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll a[MAXN];
ll d[MAXN];
ll t[MAXN];
void update(int x,int k,int n)
{
    while(x<=n)
    {
        t[x]+=k;
        t[x]=t[x]%2;
        x+=lowbit(x);
    }
}
ll query(int x,int n)
{
    ll ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
        ans%=2;
    }
    return ans;
}
void build(int n)
{
    for(int i=1;i<=n;i++)
    {
        t[i]+=d[i];
        int j=i+lowbit(i);
        if(j<=n)
        {
            t[j]+=t[i];
            t[j]=t[j]%2;
        }
    }
}
void solve()
{
    int n,m;    std::cin>>n>>m;
    build(n);
    for(int i=1;i<=m;i++)
    {
        int opt;    std::cin>>opt;
        if(opt==1)
        {
            int l,r;    std::cin>>l>>r;
            update(l,1,n);
            update(r+1,1,n);
        }
        if(opt==2)
        {
            int x;  std::cin>>x;
            std::cout<<query(x,n)<<"\n";
        }
    }

}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}

P3368 【模板】树状数组 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=5e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int a[MAXN];
int d[MAXN];
int t[MAXN];
//树状数组
//这里要求实现的是单点查询 区间修改
//我们可以发现 我们进行求一个差分数组 然后在树状数组上维护即可
void update(int x,int k,int n)
{
    while(x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}

int query(int x)
{
    int ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
//建树 O(n)建树
void build(int n)
{
    for(int i=1;i<=n;i++)
    {
        t[i]+=d[i];
        int j=i+lowbit(i);
        if(j<=n)    t[j]+=t[i];
    }
}
void solve()
{
    int n,m;    std::cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
        d[i]=a[i]-a[i-1];
    }
    build(n);
    for(int i=1;i<=m;i++)
    {
        int opt;    std::cin>>opt;
        if(opt==1)
        {
            int x,y,k;  std::cin>>x>>y>>k;
            update(x,k,n);
            update(y+1,-k,n);
        }
        if(opt==2)
        {
            int x;  std::cin>>x;
            std::cout<<query(x)<<"\n";
        }
    }
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}

P2068 统计和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll d[MAXN];
ll t[MAXN];
void update(int x,ll k,int n)
{
    while(x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}
ll query(ll x)
{
    ll ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
void build(int n)
{
    for(int i=1;i<=n;i++)
    {
        t[i]+=d[i];
        int j=i+lowbit(i);
        if(j<=n)
        {
            t[j]+=t[i];
        }
    }
}
void solve()
{
    int n,w;    std::cin>>n>>w;
    build(n);
    for(int i=1;i<=w;i++)
    {
        char opt;   std::cin>>opt;
        if(opt=='x')
        {
            int a,b;  std::cin>>a>>b;
            update(a,b,n);
        }
        if(opt=='y')
        {
            int a,b;  std::cin>>a>>b;
            std::cout<<query(b)-query(a-1)<<"\n";
        }
    }
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}

P4939 Agent2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=1e7+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll t[MAXN];
void update(int x,ll k,int n)
{
    while(x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}
ll query(int x)
{
    ll ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
void solve()
{
    int n,m;    std::cin>>n>>m;
    while(m--)
    {
        int opt;    std::cin>>opt;
        if(opt==0)
        {
            int a,b;    std::cin>>a>>b;
            update(a,1,n);
            update(b+1,-1,n);
        }
        if(opt==1)
        {
            int a;  std::cin>>a;
            std::cout<<query(a)<<"\n";
        }
    }

}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}

P2880 [USACO07JAN] Balanced Lineup G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll a[MAXN];
ll t1[MAXN];
ll t2[MAXN];
//学到了树状数组的新用法 维护区间max和区间min
//update函数还是差不多的 只不过t[i]+=k 改成了t[i]=max(t[i],k) 这里的k对应的就是a[i]
//但是query的时候需要考虑l和r 不像以前那样[1,r]-[1,l]
//我们知道 树状数组是将数组分为若干个区间 进而往上爬更新实现的 区间只包含而不相交
//那么我们可以按照熟悉的方法 一直从r-=lowbit(r)进行更新 只需要>=l即可
//但是需要注意 可能最后的块不是完整的一块 所以我们需要在不满足的条件下从r->l 直接暴力即可
void update(int x,ll k,int n)
{
    while(x<=n)
    {
        t1[x]=std::max(t1[x],k);
        t2[x]=std::min(t2[x],k);
        x+=lowbit(x);
    }
}
ll query(int l,int r)
{
    ll maxn=0;
    ll minn=0x3f3f3f3f;
    while(l<=r)
    {
        while(r-lowbit(r)>=l)
        {
            maxn=std::max(maxn,t1[r]);
            minn=std::min(minn,t2[r]);
            r-=lowbit(r);
        }
        maxn=std::max(maxn,a[r]);
        minn=std::min(minn,a[r]);
        r--;
    }
    return maxn-minn;
}
void build(int n)
{
    for(int i=1;i<=n;i++)
    {
        update(i,a[i],n);
    }
}
void solve()
{
    memset(t2,0x3f,sizeof(t2));
    int n,q;    std::cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
    }
    build(n);
    while(q--)
    {
        int x,y;    std::cin>>x>>y;
        std::cout<<query(x,y)<<"\n";
    }
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}

P6225 [eJOI2019] 异或橙子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=1e7+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll a[MAXN];
//思路都想对了 可是不会写qwq
//这题求的是^
//不难发现 如果区间包含的元素个数是偶数 那么它们的区间异或和一定为0
//反之 只跟 a[i]^a[i+2]^...^a[j] 有关
//那么我们可以在此基础上分奇偶项建立树状数组维护
//注意将a[i]修改为j的时候 t[x]^=(a[i]^k) 这个是异或的性质 注意一下即可
//query时直接异或和即可 因为分了奇偶
//至于query时 是奇数项的树状数组还是偶数项的树状数组 我们对l&1即可
struct BIT
{
    ll t[MAXN];
    void update(int x,ll k,int n)
    {
        while(x<=n)
        {
            t[x]^=k;
            x+=lowbit(x);
        }
    }
    ll query(int x)
    {
        ll ans=0;
        while(x)
        {
            ans^=t[x];
            x-=lowbit(x);
        }
        return ans;
    }
};
BIT tree[2];
void solve()
{
    int n,q;    std::cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
        tree[i&1].update(i,a[i],n);
    }
    while(q--)
    {
        int opt;    std::cin>>opt;
        if(opt==1)
        {
            int i,j;  std::cin>>i>>j;
            tree[i&1].update(i,a[i]^j,n),    a[i]=j;
        }
        if(opt==2)
        {
            int l,r;    std::cin>>l>>r;
            if((l+r)&1)     std::cout<<0<<"\n";
            else    std::cout<<(tree[l&1].query(r)^tree[l&1].query(l-1))<<"\n";
        }
    }
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}

P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=5e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
struct node
{
    ll val;
    int id;
}a[MAXN];
bool cmp(node a,node b)
{
    if(a.val!=b.val)    return a.val<b.val;
    return a.id<b.id;
}
ll b[MAXN];
ll t[MAXN];
//求解逆序对
//只需要从左往右遍历，寻找左侧比当前元素大的元素个数，叠加即可
//左侧比当前元素大的元素个数=左侧元素个数-左侧小于等于当前元素的元素个数
//后者可以使用桶排的方法
//需要涉及到离散化 暂时还不熟悉
void update(ll x,int k,int n)
{
    while(x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}
ll query(ll x)
{
    ll ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
void build(int n)
{
    for(int i=1;i<=n;i++)   update(b[i],1,n);   //相当于桶排中的t[b[i]]++;
}
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i].val, a[i].id=i;
    std::sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        b[a[i].id]=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        update(b[i],1,n);
        ans+=i-query(b[i]);
    }
    std::cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}

P1774 最接近神的人 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=5e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
struct node
{
    ll val;
    int id;
}a[MAXN];
bool cmp(node a,node b)
{
    if(a.val!=b.val)    return a.val<b.val;
    return a.id<b.id;
}
ll b[MAXN];
ll t[MAXN];
//求解逆序对
//只需要从左往右遍历，寻找左侧比当前元素大的元素个数，叠加即可
//左侧比当前元素大的元素个数=左侧元素个数-左侧小于等于当前元素的元素个数
//后者可以使用桶排的方法
//需要涉及到离散化 暂时还不熟悉
void update(ll x,int k,int n)
{
    while(x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}
ll query(ll x)
{
    ll ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
void build(int n)
{
    for(int i=1;i<=n;i++)   update(b[i],1,n);   //相当于桶排中的t[b[i]]++;
}
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i].val, a[i].id=i;
    std::sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        b[a[i].id]=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        update(b[i],1,n);
        ans+=i-query(b[i]);
    }
    std::cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}

P4378 [USACO18OPEN] Out of Sorts S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using ll=long long;
const int N=5e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll t[MAXN];
//一道逆序对的变式题 但是题目有点意思 自己犯了一些小错误
//这道题其实求的还是逆序对 但是我们可以发现
//前面那些大的数肯定会被当前数的后面，且只有这些数会跑到当前数的后面，所以这个点肯定只会被更新有限次
//那么我们取最大的即可
//1 update时 是b[i]而不是i query也是一样
//2 需要边建树 边更新答案
struct node
{
    ll val;
    int id;
    static bool cmp(node a,node b)
    {
        if(a.val==b.val)  return a.id<b.id;
        return a.val<b.val;
    }
}a[MAXN];
ll b[MAXN];
void update(ll x,ll k,int n)
{
    while(x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}
ll query(ll x,int n)
{
    ll ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
void build(int n)
{
    for(int i=1;i<=n;i++)
    {
        update(b[i],1,n);
    }
}
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i].val, a[i].id=i;
    std::sort(a+1,a+1+n,node::cmp);
    for(int i=1;i<=n;i++)
    {
        b[a[i].id]=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        update(b[i],1,n);
        ans=std::max(ans,i-query(b[i],n));
    }
    std::cout<<ans+1<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int tt=1;
    //std::cin>>t;
    while(tt--)solve();
    return 0;
}