P3368 【模板】树状数组 2 题解

本文主要是介绍P3368 【模板】树状数组 2 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】

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

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

2. 求出某一个数的值。

【Input】

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

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

接下来 M 行每行包含 2 或 4 个整数，表示一个操作，具体如下：

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

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

【Output】

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

【Sample Input】

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

【Sample Output】

6
10

【Solution】

树状数组的区间修改+单点查询

此乃某大佬的思路~ 

因为查询对象仅为一个数，那么我们就可以定义一个数组c，令c[1]+…+c[i]=a[i]，然后对c建一个树状数组，区间加值时，只需修改左端点的值。因为修改了一个点的值，后面点的值都会受影响。但如果要只使区间的数受影响，就要使右端点后一个数恢复原值，。

输出第x个数，其实就是求c[1…x]的和。

【Code】

#include<iostream>
#include<cstdio>
using namespace std;
long long tree[1000000],a[510000],bb;
int n,m,op,aa,l,r;
inline int lowbit(int x){return x&(-x);}
inline void update(int x,long long c){while(x<=n){tree[x]+=c;x+=lowbit(x);}
}
inline long long Ask(int x){long long res=0;while(x>=1){res+=tree[x];x-=lowbit(x);}return res;
}
int main(){scanf("%d%d",&n,&m);for(register int i=1;i<=n;i++){scanf("%lld",&a[i]);update(i,a[i]-a[i-1]);}for(register int i=1;i<=m;i++){scanf("%d",&op);if(op==1){scanf("%d%d%lld",&l,&r,&bb);update(l,bb);update(r+1,-bb);}else{scanf("%d",&aa);printf("%lld\n",Ask(aa));}}return 0;
}

这篇关于P3368 【模板】树状数组 2 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---