「CODEVS1080」线段树练习1(线段树 / 树状数组 / zkw线段树)
题目描述 Description
一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数m<10000条。
输入描述 Input Description
输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整数m，再接下来有m行，表示m个询问，第一个整数表示询问代号，询问代号1表示增加，后面的两个数x和A表示给位置X上的数值增加A，询问代号2表示区间求和，后面两个整数表示a和b，表示要求[a,b]之间的区间和。
输出描述 Output Description
共m行，每个整数
样例输入 Sample Input
6
4
5
6
2
1
3
4
1 3 5
2 1 4
1 1 9
2 2 6
样例输出 Sample Output
22
22
数据范围及提示 Data Size & Hint
1≤N≤100000， m≤10000 。
代码
树状数组
| 45ms | 2064kb | C++ | 797B |
|
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 |
#include<cstdio> #include<iostream> using namespace std; int n, m; int a[100001]; int lowbit(int x) { return x&(-x); } void update(int x, int num) { while(x<=n) { a[x]+=num; x+=lowbit(x); } } int sum(int x) { int sum=0; while(x>0) { sum+=a[x]; x-=lowbit(x); } return sum; } int main() { int i,j,temp; int a,x,y; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&temp); update(i,temp); } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&x,&y); if(a==1)update(x, y); else printf("%d\n",sum(y)-sum(x-1)); } return 0; } |
线段树
| 51ms | 6752kb | C++ | 1076B |
|
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<cstdio> #include<iostream> using namespace std; struct data{ int l,r,sum; }tr[400000]; int n,m,a[100001]; void build(int k,int s,int t) { tr[k].l=s;tr[k].r=t; if(s==t){tr[k].sum=a[s];return;} int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } int sum(int s,int t,int k) { int l=tr[k].l,r=tr[k].r; if(s==l&&r==t)return tr[k].sum; int mid=(l+r)>>1; if(t<=mid)return(sum(s,t,k<<1)); if(s>mid)return(sum(s,t,k<<1|1)); return (sum(s,mid,k<<1)+sum(mid+1,t,k<<1|1)); } void update(int k,int x,int y) { tr[k].sum+=y; int l=tr[k].l,r=tr[k].r; if(l==r)return; int mid=(l+r)>>1; if(x<=mid)update(k<<1,x,y); else update(k<<1|1,x,y); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&m); for(int i=1;i<=m;i++) { int temp,x,y; scanf("%d%d%d",&temp,&x,&y); if(temp==1)update(1,x,y); else printf("%d\n",sum(x,y,1)); } } |
zkw线段树！！！！！ 太神了！
| 53ms | 3720kb | C++ | 698B |
|
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 |
#include<cstdio> #include<iostream> #define M 261244 using namespace std; int tr[524289]; void query(int s,int t) { int ans=0; for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1) { if(~s&1)ans+=tr[s^1]; if(t&1)ans+=tr[t^1]; } printf("%d\n",ans); } void change(int x,int y) { for(tr[x+=M]+=y,x>>=1;x;x>>=1) tr[x]=tr[x<<1]+tr[x<<1|1]; } int main() { int n,m,f,x,y; scanf("%d",&n); for(int i=1;i<=n;i++){scanf("%d",&x);change(i,x);} scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&f,&x,&y); if(f==1)change(x,y); else query(x,y); } return 0; } |
计数器 9302376
OI 课件=>
OI 课件=>
数据太小了吧
ZKW怎么回比朴素线段树还慢？
恩恩