首页 > 代码库 > CODEVS线段树小结
CODEVS线段树小结
CODEVS1369 xth 砍树
题目大意：区间查询和，单点修改区间中点。
思路：比较简单的线段树，可是在double和float上栽了跟头，以后统一用double，输出printf里面用f，不要用llf（我zuo）。
#include<iostream>#include<cstdio>using namespace std;int tree[800000]={0},a[200001]={0};void build(int i,int l,int r){ int mid; if (l==r) { tree[i]=a[l]; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i]=tree[i*2]+tree[i*2+1];}int work(int i,int l,int r,int aa,int b){ int mid,sum=0; if (aa<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (aa<=mid) sum+=work(i*2,l,mid,aa,b); if (b>mid) sum+=work(i*2+1,mid+1,r,aa,b); return sum;}void insert(int i,int l,int r,int aa){ int mid; if (l==r&&l==aa) { tree[i]=0; return; } mid=(l+r)/2; if (aa<=mid) insert(i*2,l,mid,aa); else insert(i*2+1,mid+1,r,aa); tree[i]=tree[i*2]+tree[i*2+1];}int main(){ int n,m,i,j,l,r,sum; double ans; scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&m); for (i=1;i<=m;++i) { scanf("%d%d",&l,&r); sum=work(1,1,n,l,r); insert(1,1,n,(l+r)/2); ans=sum*3.14; printf("%0.2f\n",ans); }}
CODEVS1690 开关灯
题目大意：区间置反，区间查询。
思路：用delta数组表示区间置反的状态，这里就有出现了一个小问题，对于delta数组的思想不够了解，认识不够深入，其实delta数组表示的是这个节点的状态的累加，在每次pushdown的时候会将这个状态推至孩子，自己的状态清为0（大多数），所以在这个程序的paint中，delta[i]=!delta[i]，而不是delta[i]=0。以后应该好好理解最基本的东西，注意细节。
#include<iostream>#include<cstdio>using namespace std;int tree[400000]={0},delta[400000]={0};void paint(int i,int l,int r){ tree[i]=r-l+1-tree[i]; delta[i]=!delta[i];}void pushdown(int i,int l,int r){ int mid; mid=(l+r)/2; paint(i*2,l,mid); paint(i*2+1,mid+1,r); delta[i]=0;}void insert(int i,int l,int r,int a,int b){ int mid; if (a<=l&&r<=b) { paint(i,l,r); return; } if (delta[i]==1) pushdown(i,l,r); mid=(l+r)/2; if (a<=mid) insert(i*2,l,mid,a,b); if (b>mid) insert(i*2+1,mid+1,r,a,b); tree[i]=tree[i*2]+tree[i*2+1];}int work(int i,int l,int r,int a,int b){ int mid,sum=0; if (a<=l&&r<=b) return tree[i]; if (delta[i]==1) pushdown(i,l,r); mid=(l+r)/2; if (a<=mid) sum+=work(i*2,l,mid,a,b); if (b>mid) sum+=work(i*2+1,mid+1,r,a,b); return sum;}int main(){ int n,m,i,j,l,r,ans; scanf("%d%d",&n,&m); for (i=1;i<=m;++i) { scanf("%d%d%d",&j,&l,&r); if (j==0) insert(1,1,n,l,r); else { ans=work(1,1,n,l,r); printf("%d\n",ans); } }}
CODEVS线段树小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。