首页 > 编程语言 > 详细

树状数组习题(一本通)

时间:2020-04-19 18:11:15      阅读:86      评论:0      收藏:0      [点我收藏+]

1535:【例 1】数列操作

模板题

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=101000;
const int INF=0x3fffffff;
typedef long long LL;
#define lowbit(x)  ((x)&(-x))
int tree[maxn];
int n,m;
void add(int x,int d){
	while(x<=n){
		tree[x]+=d;
		x+=lowbit(x);
	}
}
LL getsu(int x){
	LL ans=0;
	while(x>0){
		ans+=tree[x];
		x-=lowbit(x);
	}
	return ans;
}
int main(){
	
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) {
		int x;
		scanf("%d",&x);
		add(i,x);
	}
	int k,a,b;
	while(m--){
		scanf("%d %d %d",&k,&a,&b);
		if(k==0) printf("%lld\n",getsu(b)-getsu(a-1));
		else add(a,b);
	}
return 0;
}

  

1536:【例 2】数星星 Stars

//二维的树状数组bushi
//认真读题呀!!!!!看给出数据的特征,是按照纵坐标从小到大排序的,纵坐标相同的是横坐标从小到大给出的
//也就是说,我们可以不管纵坐标,按照它给出的横坐标依次插入,并统计当前星星之前的横坐标小于它的星星个数。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
int c[100005];
int ans[100055];
int maxn=32001;
struct node{
	int x,y;
}a[100005];
int lowbit(int x)
{
	return x&(-x);
}
void update(int x,int y)
{
	while(x<=maxn)
	{
		c[x]+=y;
		x+=lowbit(x);
	}
}
int sum(int x)
{
	int cnt=0;
	while(x>0)
	{
		cnt+=c[x];
		x-=lowbit(x);
	}
	return cnt;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	for(int i=1;i<=n;i++)
	{
		int wzx=a[i].x+1;
		int jd=sum(wzx);
		update(wzx,1);
		ans[jd]++; 
	}
	for(int i=0;i<n;i++)
	printf("%d\n",ans[i]);
	return 0;
} 

  

树状数组习题(一本通)

原文:https://www.cnblogs.com/shirlybaby/p/12732595.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!