ICPC 2018 徐州网络预赛 H Ryuji doesn't want to study

【题目链接】

样例输入
5 3
1 2 3 4 5
1 1 3
2 5 0
1 4 5
样例输出
10
8

解题思路

一个树状数组维护前缀和，另一个树状数组维护(n-i+1)*aa[i]

AC代码

#include <iostream>
#define ll long long
using namespace std;
ll c1[100005], c2[100005], aa[100005];
ll lowbit(ll k)
{
    return k & (-k);
}
void update1(ll k,ll x)
{
    while (k < 100005)
    {
        c1[k] += x;
        k += lowbit(k);
    }
}
ll query1(ll k)
{
    ll ans = 0;
    while (k > 0)
    {
        ans += c1[k];
        k -= lowbit(k);
    }
    return ans;
}
void update2(ll k, ll x)
{
    while (k < 100005)
    {
        c2[k] += x;
        k += lowbit(k);
    }
}
ll query2(ll k)
{
    ll ans = 0;
    while (k > 0)
    {
        ans += c2[k];
        k -= lowbit(k);
    }
    return ans;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &aa[i]);
        update1(i, aa[i]);
        update2(i, (n - i + 1)*aa[i]);
    }
    int op;
    ll a, b;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%lld%lld", &op, &a, &b);
        if (op == 1)
        {
            ll ans;
            ll tt1 = query2(b) - query2(a - 1);
            ll tt2 = query1(b) - query1(a - 1);
            ans = tt1 - tt2 * (n - b);
            printf("%lld\n", ans);
        }
        else
        {
            update1(a, b - aa[a]);
            update2(a, (b - aa[a])*(n - a + 1));
            aa[a] = b;//更改原数组，以防下次修改
        }
    }
}