AcWing 242. 一个简单的整数问题 / 树状数组区间修改区间查询模板题

AcWing 242. 一个简单的整数问题

// 实例化是抽象的天敌，是抽象的克星
// 通过公式 sn = (i 从 1 ~ n 求积) di * (1 + n) - (i 从 1 ~ n 求积) i * di 
// 来计算前缀和, 又 (i 从 1 ~ n 求积) i * di 不能由 (i 从 1 ~ n 求积) di * (1 + n) 推出
// 所以除了维护 d 数组，还需维护 i*di 数组
// 如果是一次修改多次查询可选前缀和来做，时间复杂度 O(n)
// 但这里是多次修改多次查询, 为控制最高时间复杂度不达到 O(n^2)
// 需用树状数组来做, 时间复杂度为 O(n)

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
typedef long long LL;

LL a[N], trd[N], trdi[N];
int n, m;

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

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

LL sum(LL tr[], int u)
{
    LL ans = 0;
    for (int i = u; i > 0; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        cin >> a[i];
        add(trd, i, a[i] - a[i - 1]), add(trdi, i, (a[i] - a[i - 1]) * i);
    }

    while (m -- )
    {
        char c;
        
        cin >> c;
        
        if (c == 'Q') 
        {
            int x, y;
            cin >> x >> y;
            // 这里是 (y + 1) *, 不是 (n + 1) *             这里是 x *, 不是 (n + 1) *       
            cout << ((y + 1) * sum(trd, y) - sum(trdi, y)) - (x * sum(trd, x - 1) - sum(trdi, x - 1)) << '\n';
        }else
        {
            int x, y, c;
            cin >> x >> y >> c;
            
            add(trd, x, c), add(trd, y + 1, -c);
            add(trdi, x, c * x), add(trdi, y + 1, -c * (y + 1));
        }
    }

      
    return 0;
}