打卡信奥刷题（2716）用C++实现信奥题 P3368 【模板】树状数组 2

P3368 【模板】树状数组 2

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上xxx；

2. 求出某一个数的值。

输入格式

第一行包含两个整数NNN、MMM，分别表示该数列数字的个数和操作的总个数。

第二行包含NNN个用空格分隔的整数，其中第iii个数字表示数列第 $i $ 项的初始值。

接下来MMM行每行包含222或444个整数，表示一个操作，具体如下：

操作111： 格式：1 x y k含义：将区间[x,y][x,y][x,y]内每个数加上kkk；

操作222： 格式：2 x含义：输出第xxx个数的值。

输出格式

输出包含若干行整数，即为所有操作222的结果。

输入输出样例 #1

输入 #1

5 5 1 5 4 2 3 1 2 4 2 2 3 1 1 5 -1 1 3 5 7 2 4

输出 #1

6 10

说明/提示

样例 1 解释：

故输出结果为666和101010。

数据规模与约定

对于30%30\%30%的数据：N≤8N\le8N≤8，M≤10M\le10M≤10；

对于70%70\%70%的数据：N≤104N\le 10^4N≤104，M≤104M\le10^4M≤104；

对于100%100\%100%的数据：1≤N,M≤5×1051 \leq N, M\le 5\times10^51≤N,M≤5×105，1≤x,y≤n1 \leq x, y \leq n1≤x,y≤n，保证任意时刻序列中任意元素的绝对值都不大于2302^{30}230。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=5e5+10;intn,m,a[N];longlongc[N];// 注意 c 中的值可能超过 int 范围intlowbit(intx){returnx&(-x);}voidadd(intx,intk){// 修改操作while(x<=n){c[x]+=k;x+=lowbit(x);}return;}longlongsum(intx){// 查询操作longlongres=0;while(x){res+=c[x];x-=lowbit(x);}returnres;}intmain(){cin>>n>>m;for(inti=1;i<=n;++i){cin>>a[i];add(i,a[i]-a[i-1]);// 按照差分含义初始化}while(m--){intop;cin>>op;if(op==1){intl,r,k;cin>>l>>r>>k;add(l,k),add(r+1,-k);// 差分操作}else{intx;cin>>x;cout<<sum(x)<<"\n";// 前 x 个数的和}}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容