树状数组的神操作QAQ

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

卧槽

厉害了，我的树状数组

1、单点修改，单点查询

用差分数组维护

#include<cstdio>

#include<iostream>

using namespace std;

#define int long long

#define M 1000500

#define love_nmr 0

#define lowbit(x) (x&(-x))

int c[M],flag,n,m;

inline void add(int pos,int x)

{

    for(int i=pos;i<=n;i+=lowbit(i))

        c[i]+=x;

}

inline int query(int x)

{

    int ans=;

    for(int i=x;i;i-=lowbit(i))

        ans+=c[i];

    return ans;

}

signed main()

{

    ios::sync_with_stdio(false);

    cin>>n>>m;

    int now=,last=;

    for(int i=;i<=n;i++)

    {

        cin>>now;

        add(i,now-last);

        last=now;

    }

    int x;

    for(int i=;i<=m;i++)

    {

        cin>>flag;

        if(flag==)

        {

            int x,k;

            cin>>x>>k;

            add(x,k);

            add(x+,-k);

        }

        else

        {

            cin>>x;

            cout<<query(x)<<endl;

        }

    }

    return love_nmr;

}

2、单点修改，区间查询（最原始的，最本质的）

#include<cstdio>

#include<iostream>

using namespace std;

#define N 1000050

#define int long long

#define love_nmr 0

int a[N],c[N],j;

int n,m;

inline int lowbit(int x)

{

    return x&(-x);

}

inline void add(int x,int y)

{

    while(x<=n)

    {

        c[x]+=y;

        x+=lowbit(x);

    }

}

inline int sum(int x)

{

    int ace=;

    while(x>=)

    {

        ace+=c[x];

        x-=lowbit(x);

    }

    return ace;

}

signed main()

{

    ios::sync_with_stdio(false);

    cin>>n>>m;

    int x,y;

    for(int i=;i<=n;i++)

    {

        cin>>a[i];

        add(i,a[i]);

    }

    for(int i=;i<=m;i++)

    {

        cin>>j>>x>>y;

        if(j==)

            add(x,y);

        else

            cout<<sum(y)-sum(x-)<<endl;

    }

    return love_nmr;

}

3、区间修改，单点查询

差分应用

#include<cstdio>

#include<iostream>

using namespace std;

#define int long long

#define M 1000500

#define love_nmr 0

#define lowbit(x) (x&(-x))

int c[M],flag,n,m;

inline void add(int pos,int x)

{

    for(int i=pos;i<=n;i+=lowbit(i))

        c[i]+=x;

}

inline int query(int x)

{

    int ans=;

    for(int i=x;i;i-=lowbit(i))

        ans+=c[i];

    return ans;

}

signed main()

{

    ios::sync_with_stdio(false);

    cin>>n>>m;

    int now=,last=;

    for(int i=;i<=n;i++)

    {

        cin>>now;

        add(i,now-last);

        last=now;

    }

    int x;

    for(int i=;i<=m;i++)

    {

        cin>>flag;

        if(flag==)

        {

            int x,y,k;

            cin>>x>>y>>k;

            add(x,k);

            add(y+,-k);

        }

        else

        {

            cin>>x;

            cout<<query(x)<<endl;

        }

    }

    return love_nmr;

}

4、区间修改，区间查询（niubilitiful）

观察式子：
a[1]+a[2]+...+a[n]

= (c[1]) + (c[1]+c[2]) + ... + (c[1]+c[2]+...+c[n])

= n*c[1] + (n-1)*c[2] +... +c[n]

= n * (c[1]+c[2]+...+c[n]) - (0*c[1]+1*c[2]+...+(n-1)*c[n]) (式子①)

那么我们就维护一个数组c2[n]，其中c2[i] = (i-1)*c[i]

每当修改c的时候，就同步修改一下c2，这样复杂度就不会改变

那么

式子①

$=n*\sum{(c,n)} - \sum{(c2,n)}$

于是我们做到了在O(logN)的时间内完成一次区间和查询

#include<cstdio>

#include<iostream>

using namespace std;

#define int long long

#define M 1000500

#define love_nmr 0

#define lowbit(x) (x&(-x))

int c[M],flag,n,m;

int s[M];

inline void add(int pos,int x)

{

    for(int i=pos;i<=n;i+=lowbit(i))

    {

        c[i]+=x;

        s[i]+=(pos-)*x;

    }

}

inline int queryc(int x)

{

    int ans=;

    for(int i=x;i;i-=lowbit(i))

        ans+=c[i];

    return ans;

}

inline int querys(int x)

{

    int ans=;

    for(int i=x;i;i-=lowbit(i))

        ans+=s[i];

    return ans;

}

signed main()

{

    ios::sync_with_stdio(false);

    cin>>n>>m;

    int now=,last=;

    for(int i=;i<=n;i++)

    {

        cin>>now;

        add(i,now-last);

        last=now;

    }

    for(int i=;i<=m;i++)

    {

        cin>>flag;

        if(flag==)

        {

            int x,y,k;

            cin>>x>>y>>k;

            add(x,k);

            add(y+,-k);

        }

        else

        {

            int x,y;

            cin>>x>>y;

            int tot1=y*queryc(y)-querys(y);

            int tot2=(x-)*queryc(x-)-querys(x-);

            cout<<tot1-tot2<<endl;

        }

    }

    return love_nmr;

}