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

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

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

作者：

秦淮岸灯火阑珊 , 2019-02-13 20:05:25 , 所有人可见 , 阅读 4109

25

5

原题链接
 更好的阅读体验

题目描述

给定长度为N的数列A，然后输入M行操作指令。

第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。

第二类指令形如“Q X”，表示询问数列中第x个数的值。

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

输入格式
第一行包含两个整数N和M。

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

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

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

每个答案占一行。

数据范围
$1 \le N,M \le 10^5$,
$|d| \le 10000$,
$|A[i]| \le 1000000000$

样例

输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2
输出样例：
4
1
2
5

树状数组(区间修改,单点查询)

树状数组只支持单点查询,但是这里我们要资瓷区间操作,那么就得来一点特殊操作.

首先我们可以开一个数组B,然后对于每条C操作,我们直接利用前缀和的思想.

把b[l]+=d;
把b[r+1]-=d;

然后我们就成功达成成就,把维护序列的具体值,转化为维护指令的累计影响,每次操作的影响,在l处开始,然后在r+1处消除.然后就让单点修改可以维护区间修改.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define lowbit(x) x&(-x)
int a[N],c[N],b[N],i,j,n,m;
inline int ask(int x)
{
    int ans=a[x];
    for(;x;x-=lowbit(x))
        ans+=c[x];
    return ans;
}
inline void add(int x,int y)
{
    for(;x<=n;x+=lowbit(x))
        c[x]+=y;
}
int main()
{
    scanf("%d%d\n",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    getchar();
    for(i=1;i<=m;i++)
    {
        char ch=getchar();
        if (ch=='C')
        {
            int l,r,d;
            scanf("%d%d%d\n",&l,&r,&d);
            add(l,d);
            add(r+1,-d);//前缀和思想
        }
        if (ch=='Q')
        {
            int x;
            scanf(" %d\n",&x);
            printf("%d\n",ask(x));
        }
    }
    return 0;
}

14 评论

1565984662 2022-04-03 19:47

刚刚学算法的初中生，问这个b数组起到了什么作用咩？

_27 2022-06-29 16:04

差分数组

沐枫. 2019-08-18 21:04

为什么不能一开始没输入一个a接着做差分，再后续对这个差分数组进行操作呢

秦淮岸灯火阑珊 2019-08-18 21:40

其实是可以的

沐枫. 2019-08-18 22:10 回复了秦淮岸灯火阑珊的评论

我就这么写的连样例都过不了……

秦淮岸灯火阑珊 2019-08-19 07:05 回复了沐枫. 的评论

为啥啊？我觉得这个算法木有问题啊。到时我觉得我自己这个算法，不咋好。
是我老了，脑袋傻了吗？我改天修改一下，用您说的算法，做一遍啊！

cqx 2021-01-19 11:51 回复了沐枫. 的评论

用树状数组查询复杂度为 logn ，则复杂度为 m * logn，否则为 m * n 超时

糖豆 2023-08-17 16:31

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;

int n, m;
int a[N];
// 树状数组模板
typedef long long LL;
#define lowbit(x) (x & -x)
int c[N];
void add(int x, int d) {
    for (int i = x; i < N; i += lowbit(i)) c[i] += d;
}
LL sum(int x) {
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}

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

    // 方法1：也可以这么做，但是方法比较笨拙
    // 树状数组初始化，保存差分值
    // for (int i = 1; i <= n; i++) add(i, a[i] - a[i - 1]);

    while (m--) {
        char op[2];
        scanf("%s", op);

        if (op[0] == 'C') { // 修改
            int l, r, d;
            scanf("%d %d %d", &l, &r, &d);
            // 差分，在l处加上d,在r+1位置减去d
            add(l, d), add(r + 1, -d);
        } else {
            int l;
            scanf("%d", &l);
            // 方法1
            // printf("%lld\n", sum(l)); // 求前缀和
            // 推荐方法
            printf("%lld\n", a[l] + sum(l)); // 求前缀和
        }
    }
    return 0;
}

把注释的方法1打开就是这样的办法了