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

1.將某一個數(shù)加上x

2.求出某區(qū)間每一個數(shù)的和

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

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

接下來M行每行包含3個整數(shù)，表示一個操作，具體如下：

操作1： 格式：1 x k 含義：將第x個數(shù)加上k

操作2： 格式：2 x y 含義：輸出區(qū)間[x,y]內(nèi)每個數(shù)的和

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

輸入輸出樣例
輸入樣例#1： 復(fù)制
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
輸出樣例#1： 復(fù)制
14
16
說明
時空限制：1000ms,128M

數(shù)據(jù)規(guī)模：

對于30%的數(shù)據(jù)：N<=8，M<=10

對于70%的數(shù)據(jù)：N<=10000，M<=10000

對于100%的數(shù)據(jù)：N<=500000，M<=500000

樣例說明：

故輸出結(jié)果14、16
.
.
.
.
.

程序：

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> using namespace std; int n,m,tree[2000010]; int lowbit(int k) {return k & -k; } void add(int x,int k) {while(x<=n){tree[x]+=k;x+=lowbit(x);} } int sum(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++){int a;scanf("%d",&a);add(i,a);}for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(a==1) add(b,c);if(a==2) cout<<sum(c)-sum(b-1)<<endl;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10292860.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。