「CODEVS1081」线段树练习 2(线段树 / 树状数组)
题目描述 Description
给你N个数，有两种操作
1：给区间[a,b]的所有数都增加X
2：询问第i个数是什么？
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 3
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
数据范围
1<=n<=100000
1<=q<=100000
代码
线段树
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<iostream> #include<cstdio> using namespace std; int n,q,a[100001]; struct data{ int l,r,x; }tr[400001]; void build(int k,int s,int t) { tr[k].l=s;tr[k].r=t; if(s==t){tr[k].x=a[s];return;} int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); } void update(int k,int a,int b,int x) { int l=tr[k].l,r=tr[k].r; if(l==a&&b==r){tr[k].x+=x;return;} int mid=(l+r)>>1; if(b<=mid)update(k<<1,a,b,x); else if(a>mid)update(k<<1|1,a,b,x); else { update(k<<1,a,mid,x); update(k<<1|1,mid+1,b,x); } } int ask(int k,int x) { int l=tr[k].l,r=tr[k].r; if(l==r){return tr[k].x;} int mid=(l+r)>>1; if(x<=mid)return tr[k].x+ask(k<<1,x); else return tr[k].x+ask(k<<1|1,x); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&q); for(int i=1;i<=q;i++) { int t,a,b,x; scanf("%d",&t); if(t==1){ scanf("%d%d%d",&a,&b,&x); update(1,a,b,x); } else{ scanf("%d",&x); printf("%d\n",ask(1,x)); } } return 0; } |
树状数组
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstdio> using namespace std; int n,m,a[100001]; int lowbit(int x){return (-x)&x;} void update(int x,int y) { while(x<=n) { a[x]+=y; x+=lowbit(x); } } int ask(int x) { int s=0; while(x) { s+=a[x]; x-=lowbit(x); } return s; } int main() { int t,a,b,c; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a); update(i,a); } scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d",&t); if(t==1) { scanf("%d%d%d",&a,&b,&c); for(int j=a;j<=b;j++)update(j,c); } else { scanf("%d",&a); printf("%d\n",ask(a)-ask(a-1)); } } return 0; } |
Subscribe
计数器 9300099
OI 课件=>
OI 课件=>