算法提高课汇总

算法思路

在 AcWing 242. 一个简单的整数问题 的基础上更进一步, 本题需要的操作:

• 修改区间元素

• 查询区间和

修改区间元素可用差分实现$b_i = a_i - a_{i - 1}$, 考虑对于原数组前缀和的计算:

$sum(x) = \sum_{i=1}^{i=x} a_i = \sum_{i=1}^{i=x} \sum_{j=1}^{j=i} b_i$ $(a_i = \sum_{j = 1}^{j=i} b_i)$.

考虑对上述公式做进一步转化:

$sum(x) = \sum_{i=1}^{i=x} \sum_{j=1}^{j=i} b_i = x\times b_1 + (x-1)\times b_2 + … + b_x$
$\;\;= (x+1)\times \sum_{i=1}^{i=x} b_i - b_1 - 2\times b_2 - … - x\times b_x$
$\;\;= (x+1)\times \sum_{i=1}^{i=x} b_i - \sum_{i=1}^{i=x} i\times b_i$.

为快速求区间和, 我们需要维护$b_i$与$i\times b_i$的前缀和.

代码实现

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n, m;
int a[N];
ll tr1[N], tr2[N]; //维护bi 与 i x bi 的前缀和的树状数组

int lowbit(int x)
{
    return x & -x;    
}

void add(ll tr[], int x, ll c)
{
    for ( int i = x; i <= n; i += lowbit(i) )   tr[i] += c;
}

ll sum(ll tr[], int x)
{//计算树状数组前缀和
    ll res = 0;
    for ( int i = x; i; i -= lowbit(i) )    res += tr[i];
    return res;
}

ll prefix_sum(int x)
{//计算原数组a前缀和
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

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

    //树状数组初始化
    for ( int i = 1; i <= n; i ++ )
    {
        int b = a[i] - a[i - 1];
        add(tr1, i, b);  //bi
        add(tr2, i, (ll)i * b);  //i x bi
    }

    while ( m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if ( *op == 'Q' )
        {
            printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
        }
        else
        {
            scanf("%d", &d);
            //b[l] += d
            add(tr1, l, d); add(tr2, l, l * d);
            //b[r + 1] -= d
            add(tr1, r + 1, -d); add(tr2, r + 1, (r + 1) * -d);
        }
    }

    return 0;
}