线段树初识&hdu 1166 敌兵布阵

线段树初识&hdu 1166 敌兵布阵

一些区间有关的问题，给一些区间线段求并区间的长度或并区间个数当数据范围过大时会让时间复杂度过高不满足解题时间的要求。此时需要一种高效的数据结构来帮助我们。线段树正是这样的工具，它借助分而治之的思想解决子问题，再将子问题的解组合起来。有关线段树的各种操作函数均用递归函数实现：

struct node{ int left,right,mid;// other date. }seg_tree[3*maxn]; // 设置根节点下标是1，则左孩子是2*dex,右孩子下标是2*dex+1.void build(int l,int r,int num){ //建立线段树 seg_tree[num].left=l; seg_tree[num].right=r; seg_tree[num].mid=(l+r)/2; if(l==r)return ; bulid(l,seg_tree[num].mid,2*num); bulid(seg_tree[num].mid+1,r,2*num+1);}void insert(int l,int r,int num){ //插入（覆盖）需要在节点中添加一个数据cover，1表示覆盖 if(l==seg_tree[num].left&&r==seg_tree[num].right){ seg_tree[num].cover=1; return ; } if(r<=seg_tree[num].mid)insert(l,r,2*num); else if(l>=seg_tree[num].mid)insert(l,r,2*num+1); else{ insert(l,seg_tree[num].mid,2*num); insert(seg_tree[num].mid+1,r,2*num+1); }}void del(int l,int r,int num){ //删除仍然和cover联系。 if(l==seg_tree[num].left&&r==seg_tree[num].right){ seg_tree[num].cover=0; return ; } else if(seg_tree[num].cover){ seg_tree[num].cover=0; seg_tree[2*num].cover=1; seg_tree[2*num+1]cover=1; } if(rseg_tree[num].mid)del(l,r,2*num+1); else { del(l,seg_tree[num].mid,2*num); del(seg_tree[num].mid+1,r,2*num+1); }}int cal(int num){ //统计线段覆盖的长度 if(seg_tree[num].cover)return seg_tree[num].right-seg_tree[num].left+1; if(seg_tree[num].left+1==seg_tree[num].right)return 0; return cal(2*num)+cal(2*num+1);}

例题：hdu 1166 敌兵布阵 题意：详见#include#includeusing namespace std;const int maxn=5e4+5;int N,x[maxn];// 最长区间长度struct node{ int left,right,sum;}btree[3*maxn]; // 设置根节点下标是1，左孩子是2*dex,右孩子下标是2*dex+1.void build(int root,int l,int r){ // 主函数里的数组的下标对应线段树的left,right btree[root].left=l; //root对应树和各种子树的根节点 btree[root].right=r; if(l==r){ btree[root].sum=x[l]; return ; } int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); btree[root].sum=btree[2*root].sum+btree[2*root+1].sum; //递归回溯赋值给双亲结点}void update(int root,int pos,int val){ if(btree[root].left==btree[root].right){ btree[root].sum+=val; return ; } int mid=(btree[root].left+btree[root].right)/2; if(pos<=mid)update(2*root,pos,val); else update(2*root+1,pos,val); btree[root].sum=btree[root*2].sum+btree[2*root+1].sum;}int query(int root,int L,int R){ if(L<=btree[root].left&&R>=btree[root].right)return btree[root].sum; int mid=(btree[root].left+btree[root].right)/2,ans=0; if(L<=mid)ans+=query(root*2,L,R); // L,R不要弄错，否则会数组越界 if(R>mid)ans+=query(2*root+1,L,R); return ans;}int main(int argc, char *argv[]) { //freopen("cin.txt","r",stdin); int T,t=1; cin>>T; while(t<=T){ int i,j,a,b; scanf("%d",&N); char str[10]; for(i=1;i<=N;i++){ scanf("%d",&x[i]); } build(1,1,N); printf("Case %d:\n",t); while(~scanf("%s",str)&&strcmp(str,"End")){ scanf("%d%d",&a,&b); if(str[0]=='A')update(1,a,b); else if(str[0]=='S')update(1,a,-b); else printf("%d\n",query(1,a,b)); } t++; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。