转载

树状数组模板(持续更新)

树状数组题目(持续更新)

\(1.\) 树状数组 \(1\) :单点修改,区间查询

\(2.\) 树状数组 \(2\) :区间修改,单点查询

\(3.\) 树状数组 \(3\) :区间修改,区间查询

树状数组单点修改,区间查询和

$View$ $Code$
//省略头文件
using namespace std;
inline int read()
{
    int ret=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch='0'&&ch<='9')
    {
        ret=(ret<<1)+(ret<<3)+ch-'0';
        ch=getchar();
    }
    return ret*f;
}
int n,q,a[1000005],op,x,val,l,r;
long long bit[1000005];
inline long long query(int x)
{
    long long ans=0;
    for(;x;x-=x&-x)
        ans+=bit[x];
    return ans;
}
inline void modify(int x,int y)
{
    for(;x<=n;x+=x&-x)
        bit[x]+=y;
    return;
}
int main()
{
    n=read();
    q=read();
    for(register int i=1;i<=n;i++)
    {
        a[i]=read();
        modify(i,a[i]);
    }
    while(q--)
    {
        op=read();
        if(op==1)
        {
            x=read();
            val=read();
            modify(x,val);
        }
        else
        {
            l=read();
            r=read();
            printf("%lld\n",query(r)-query(l-1));
        }
    }
    return 0;
}

树状数组求逆序对(数值范围)

细节:不用预处理 \(bit\) ,序列直接倒序加进 \(bit\) 就行。

$View$ $Code$
//省略头文件
using namespace std;
inline int read()
{
    int ret=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch='0'&&ch<='9')
    {
        ret=(ret<<1)+(ret<<3)+ch-'0';
        ch=getchar();
    }
    return ret*f;
}
int n,a[1000005];
long long bit[1000005],ans;
inline long long query(int x)
{
    long long ans=0;
    for(;x;x-=x&-x)
        ans+=bit[x];
    return ans;
}
inline void modify(int x,int y)
{
    for(;x<=n;x+=x&-x)
        bit[x]+=y;
    return;
}
int main()
{
    n=read();
    for(register int i=1;i<=n;i++)
        a[i]=read();
    for(register int i=n;i;i--)
    {
        ans+=query(a[i]-1);
        modify(a[i],1);
    }
    printf("%lld\n",ans);
    return 0;
}

树状数组求逆序对(离散化)

树状数组区间修改,单点查询

树状数组区间修改,区间查询和

转载于:https://www.cnblogs.com/Peter0701/p/11437411.html

正文到此结束
本文目录