首页 > 代码库 > 洛谷——P3374 【模板】树状数组 1

洛谷——P3374 【模板】树状数组 1

https://www.luogu.org/problem/show?pid=3374

题目描述

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

1.将某一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式:

 

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

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

接下来M行每行包含3或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x k 含义:将第x个数加上k

操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
5 51 5 4 2 31 1 32 2 51 3 -11 4 22 1 4
输出样例#1:
1416

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=10000,M<=10000

对于100%的数据:N<=500000,M<=500000

样例说明:

技术分享

技术分享

 

 1 #include <cstdio> 2  3 #define lowbit(x) (x&(-x)) 4  5 using namespace std; 6  7 const int N(500000+15); 8 int n,m,x,y,tr[N]; 9 int if_,ch,od;10 11 inline void read(int &x)12 {13     if_=x=0; ch=getchar();14     for(;ch<0||ch>9;ch=getchar())15         if(ch==-) if_=1;16     for(;ch>=0&&ch<=9;ch=getchar())17         x=x*10+ch-0;18     if(if_) x=(~x)+1;19 }20 21 inline void up(int i,int x)22 {23     for(;i<=n;i+=lowbit(i)) tr[i]+=x;24 }25 26 inline int query(int x)27 {28     int ret=0;29     for(;x;x-=lowbit(x)) ret+=tr[x];30     return ret;31 }32 33 int main()34 {35     read(n); read(m);36     for(int i=1;i<=n;i++)37         read(x),up(i,x);38     for(;m;m--)39     {40         read(od); read(x);read(y);41         if(od==1) up(x,y);42         else printf("%d\n",query(y)-query(x-1));43     }44     return 0;45 }

 

故输出结果14、16

洛谷——P3374 【模板】树状数组 1