HDU1556 树状数组，线段树区间更新两种方法（主要树状数组）

本文主要是介绍HDU1556 树状数组，线段树区间更新两种方法（主要树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <stdio.h>
#include <string.h>
const int MAXN=110000;
int n,c[MAXN];
int lowbit(int x)
//计算2^k
{x=x&-x;return x;
}
void update(int num,int val)
//向下查询，num是要更新的子节点，val是要修改的值
{while(num>0){c[num]+=val;num-=lowbit(num);}
}
int getSum(int num)
//向上统计每个区间被染色的次数
{int sum=0;while(num<=n){sum+=c[num];num+=lowbit(num);}return sum;
}
int main()
{int a,b;while(scanf("%d",&n),n){memset(c,0,sizeof(c));for(int i=0;i<n;i++){scanf("%d%d",&a,&b);//将b以下区间+1update(b,1);//将a以下区间-1update(a-1,-1);}for(int j=1;j<n;j++){printf("%d ",getSum(j));}printf("%d\n",getSum(n));}return 0;
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;int ans[1000000],n;struct node
{int l,r,n;
} a[1000000];void init(int l,int r,int i)
{a[i].l = l;a[i].r = r;a[i].n = 0;if(l!=r){int mid = (l+r)>>1;init(l,mid,2*i);init(mid+1,r,2*i+1);}
}void insert(int i,int x,int y)
{if(a[i].l == x && a[i].r == y)//找到要刷的气球区间，更新其被刷的次数+1a[i].n++;else{int mid = (a[i].l+a[i].r)>>1;if(y<=mid)insert(2*i,x,y);else if(x>mid)insert(2*i+1,x,y);else{insert(2*i,x,mid);insert(2*i+1,mid+1,y);}}
}void add(int x)
{int i;for(i = a[x].l; i<=a[x].r; i++)//该区间所有编号都被刷了一次ans[i]+=a[x].n;if(a[x].l == a[x].r)return;add(2*x);add(2*x+1);
}int main()
{int x,y,i;while(~scanf("%d",&n),n){init(1,n,1);for(i = 1; i<=n; i++){scanf("%d%d",&x,&y);insert(1,x,y);}memset(ans,0,sizeof(ans));add(1);printf("%d",ans[1]);for(i = 2; i<=n; i++)printf(" %d",ans[i]);printf("\n");}return 0;
}

这篇关于HDU1556 树状数组，线段树区间更新两种方法（主要树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！