算法提高课汇总

算法思路

树状数组的基本操作为:

• 修改某个元素值.

• 计算前缀和.

即树状数组支持在线修改元素并计算前缀和.

而本题要求的操作为:

• 修改某个区间元素值.

• 计算某个元素值.

即要求我们支持在线修改和计算差分数组的前缀和. 让树状数组维护原数组的
差分数组即可.

代码实现

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], tr[N];

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

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

int sum(int x)
{
    int res = 0;
    for ( int i = x; i; i -= lowbit(i) )    res += tr[i];
    return res;
}

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 ++ ) add(i, a[i] - a[i - 1]);

    while ( m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s%d", op, &l);
        if ( *op == 'C' )
        {
            scanf("%d%d", &r, &d);
            add(l, d), add(r + 1, -d);  // 差分数组更新操作
        }
        else
        {
            printf("%d\n", sum(l));
        }
    }

    return 0;
}