树状数组求调

P3372 【模板】线段树 1

liruizhou_lihui @ 2024-11-25 01:39:47

#include<bits/stdc++.h>
using namespace std;
int n,m;
int At[1000005];
int Bt[1000005];
int lowbit(int x)
{
    return x&(-x);
}
void Aadd(int pos,int x)
{
    while(pos<=n)
    {
        At[pos]+=x;
        pos+=lowbit(pos);
    }
}
int Asum(int pos)
{
    int cnt=0;
    while(pos>0)
    {
        cnt+=At[pos];
        pos-=lowbit(pos);
    }
    return cnt;
}

void Badd(int pos,int x)
{
    while(pos<=n)
    {
        Bt[pos]+=x;
        pos+=lowbit(pos);
    }
}
int Bsum(int pos)
{
    int cnt=0;
    while(pos>0)
    {
        cnt+=Bt[pos];
        pos-=lowbit(pos);
    }
    return cnt;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        Aadd(i,x);
        Aadd(i+1,-x);
        Badd(i,x*i);
        Badd(i+1,-(x*i));
    }
    while(m--)
    {
        int q;
        cin>>q;
        if(q==1)
        {
            int x,y,k;
            cin>>x>>y>>k;
            Aadd(x,k);
            Aadd(y+1,-k);
            Badd(x,k*x);
            Badd(y+1,-(k*y));
        }
        else
        {
            int x,y;
            cin>>x>>y;
            cout<<((y+1)*Asum(y)-Bsum(y))-((x+1)*Asum(x)-Bsum(x))<<'\n';
        }
    }
    return 0;
}

设原始数组为 a，树状数组为 b。

那么

\begin{aligned} \sum_{i=1}^{x} a_i &= \sum_{i=1}^{1} b_i + \sum_{i=1}^{2} b_i + \sum_{i=1}^{3} b_i + \cdots \sum_{i=1}^{x} b_i \\ &= b_1 \times x + b_2 \times (x-1) + b_3 \times (x-2) + \cdots + b_x \times 1 \\ &= (x+1) \sum_{i=1}^{x} d_i - 1 \times d_1 -2 \times d_2 + \cdots + x \times d_x \\ &= (x+1) \sum_{i=1}^{x} d_i - \sum_{i=1}^{x} (i \times d_i) \end{aligned}

by light_searcher @ 2024-11-25 06:42:03

建议看我的文章

by Vlexander @ 2024-11-25 07:18:22

#include <iostream>
using namespace std;
const int MAXN = 2e6;
int tree[2][MAXN], n, m, a[MAXN], sum[MAXN];
inline long long lowbit(int x) { return x & (-x); }

void add(int k, int x, int y)
{
    for (int i = x; i <= n; i += lowbit(i))
        tree[k][i] += y;
}

long long find(int k, int x)
{
    long long ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans += tree[k][i];
    return ans;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }

    while (m--)
    {
        int op, x, y, k;
        scanf("%d", &op);
        scanf("%d %d", &x, &y);
        if (op == 1)
        {
            scanf("%d", &k);
            add(0, x, k);
            add(0, y + 1, -k);
            add(1, x, x * k);
            add(1, y + 1, -(y + 1) * k);
        }
        else
        {
            long long ans = sum[y] + (y + 1) * find(0, y) - find(1, y);
            ans -= sum[x - 1] + x * find(0, x - 1) - find(1, x - 1);
            printf("%lld\n", ans);
        }
    }

    return 0;
}

by Vlexander @ 2024-11-25 07:21:01

@liruizhou_lihui

忘开long long?

by Vlexander @ 2024-11-25 07:23:23

@liruizhou_lihui

如果 70分，就是忘开long long

by liruizhou_lihui @ 2024-11-25 11:52:13

#include<bits/stdc++.h>
using namespace std;
int n,m;
int At[1000005];
int Bt[1000005];
int lowbit(int x)
{
    return x&(-x);
}
void Aadd(int pos,int x)
{
    while(pos<=n)
    {
        At[pos]+=x;
        pos+=lowbit(pos);
    }
}
int Asum(int pos)
{
    int cnt=0;
    while(pos>0)
    {
        cnt+=At[pos];
        pos-=lowbit(pos);
    }
    return cnt;
}

void Badd(int pos,int x)
{
    while(pos<=n)
    {
        Bt[pos]+=x;
        pos+=lowbit(pos);
    }
}
int Bsum(int pos)
{
    int cnt=0;
    while(pos>0)
    {
        cnt+=Bt[pos];
        pos-=lowbit(pos);
    }
    return cnt;
}
 /*
((y+1ll)*Asum(y)-Bsum(y))-((x+1ll)*Asum(x)-Bsum(x))
*/
int getSum(int p)
{
    return (p+1LL)*Asum(p)-Bsum(p);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        Aadd(i,x);
        Aadd(i+1,-x);
        Badd(i,x*(i+1));
        Badd(i+1,-(x*(i+1)));
    }
    while(m--)
    {
        int q;
        cin>>q;
        if(q==1)
        {
            int x,y,k;
            cin>>x>>y>>k;
            Aadd(x,k);
            Aadd(y+1,-k);
            Badd(x,k*x);
            Badd(y+1,-(k*(y+1)));
        }
        else
        {
            int x,y;
            cin>>x>>y;
            cout<<getSum(y)-getSum(x-1)<<'\n';
        }
    }
    return 0;
}

@light_searcher@Vlexander

还不对

by Vlexander @ 2024-11-25 12:50:17

@liruizhou_lihui

尝试把开头读入给他分离出来成前缀和数组

by Always_Remember_It @ 2024-11-26 22:00:04

@liruizhou_lihui 你的刚开始的add数组需要在差分数组的基础上(即式子中的b[i])修改而不能在原数组上

改后代码

就改了个数组和加了long long