首页 > 代码库 > 线段树 模板
线段树 模板
以codevs 线段树练习1、2为例
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int n,m; 6 struct node { 7 int l,r,sum; 8 }tree[100010*4]; 9 void built(int l,int r,int k) 10 { 11 tree[k].l=l;tree[k].r=r; 12 if(l==r){ scanf("%d",&tree[k].sum);return ; } 13 int mid=(l+r)/2; 14 built(l,mid,k*2);built(mid+1,r,k*2+1); 15 tree[k].sum=tree[k*2].sum+tree[k*2+1].sum; 16 } 17 void change(int k,int pos,int x) 18 { 19 int l=tree[k].l,r=tree[k].r; 20 if(l==r){ tree[k].sum+=x;return; } 21 int mid=(l+r)/2; 22 if(pos<=mid) change(k*2,pos,x); 23 if(pos>mid) change(k*2+1,pos,x); 24 tree[k].sum=tree[k*2].sum+tree[k*2+1].sum; 25 } 26 int query(int k,int l,int r)// 区间查询(以求和为例) 27 { 28 int ans=0; 29 if(l==tree[k].l&&r==tree[k].r) { return tree[k].sum; } 30 int mid=(tree[k].l+tree[k].r)/2; 31 if(l<=mid) ans+=query(k*2,l,min(mid,r)); 32 if(r>mid) ans+=query(k*2+1,max(mid+1,l),r); 33 return ans; 34 } 35 int find(int k,int pos) 36 { 37 if(tree[k].l==tree[k].r) { return tree[k].sum; } 38 int mid=(tree[k].l+tree[k].r)/2; 39 if(pos<=mid) find(k*2,pos); 40 if(pos>mid) find(k*2+1,pos); 41 } 42 void allchange(int k,int ls,int rs,int x) 43 { 44 int l=tree[k].l,r=tree[k].r; 45 if(l==r){tree[k].sum+=x;return;} 46 int mid=(l+r)/2; 47 if(ls<=mid) allchange(k*2,ls,min(rs,mid),x); 48 if(rs>mid) allchange(k*2+1,max(ls,mid+1),rs,x); 49 } 50 int main()// 线段树 维护 区间求和 和 单点修改 51 { 52 scanf("%d",&n); 53 built(1,n,1); 54 change(1,x,a);// 在x的为位置上增加a 55 query(1,x,y); 56 find(1,x);// 单点查询x 57 allchange(1,x,y,z);//区间x到y 的值全部增加 z 58 return 0; 59 }
线段树 模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。