AcWing 243. 一个简单的整数问题2（树状数组实现区间修改+区间查询）

2022-11-26 88

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 笔记

AcWing243. 一个简单的整数问题2(树状数组实现区间修改+区间查询)

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”，表示询问数列中第 l~r 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数N,M。

第二行N个整数A[i]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n , m;
int a[N];
LL tr1[N] , tr2[N];
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)
{
    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);
        add(tr2 , i , (LL)b * i);
    }
    while(m--)
    {
        int l , r , d;
        char op[2];
        scanf("%s%d%d" , op , &l , &r);
        if(*op == 'Q')
            cout << prefix_sum(r) - prefix_sum(l - 1) << endl;
        else
        {   
            scanf("%d" , &d);
            add(tr1 , l , d) , add(tr1 , r + 1 , -d);
            add(tr2 , l , l * d) , add(tr2 , r + 1 , (r + 1) * (- d));
        }
    }
        return 0;
}