題目描述
如題，已知一個數列，你需要進行下面兩種操作：

1.將某區間每一個數數加上x

2.求出某一個數的和

輸入輸出格式
輸入格式：
第一行包含兩個整數N、M，分別表示該數列數字的個數和操作的總個數。

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

接下來M行每行包含2或4個整數，表示一個操作，具體如下：

操作1： 格式：1 x y k 含義：將區間[x,y]內每個數加上k

操作2： 格式：2 x 含義：輸出第x個數的值

輸出格式：
輸出包含若干行整數，即為所有操作2的結果。

輸入輸出樣例
輸入樣例#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
說明
時空限制：1000ms,128M

數據規模：

對于30%的數據：N<=8，M<=10

對于70%的數據：N<=10000，M<=10000

對于100%的數據：N<=500000，M<=500000

樣例說明：

故輸出結果為6、10
.
.
.
.
.

程序：

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> #include <queue> using namespace std; int n,m; int input[500010]; int tree[500100]; int lowbit(int x) {return x & -x; } void add(int x,int k) {while(x<=n){tree[x]+=k;x+=lowbit(x);} } int search(int x) {int ans=0;while(x!=0){ans+=tree[x];x-=lowbit(x);}return ans; } int main() {cin>>n>>m;for(int i=1;i<=n;i++)cin>>input[i];for(int i=1;i<=m;i++){int a;scanf("%d",&a);if(a==1){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,z);add(y+1,-z);}if(a==2){int x;scanf("%d",&x);printf("%d\n",input[x]+search(x));}}return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/10292859.html

總結

以上是生活随笔為你收集整理的洛谷 P3368 【模板】树状数组 2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。