HDU1556 Color the ball 树状数组 修改区间值 查找单点值

以前记得看到过树状数组能做的   线段树肯定可以做，反过来不行  这句话，所以没去学树状数组，现在补一下吧

看到这道题，还是手痒敲了一把线段树，可是不知道为什么超时了，改了几把还是超时，真心不知道哪里出问题了，后来看了别人的题解，发现没什么他们的跟我的没什么大区别，后来复制了他们的去交了一把，发现大家的都超时了，可能题目的数据范围被被修改了，不过还是贴出超时，代码希望路过有大神可以指点一下

还有可以先做一下POJ2309，有助于理解树状数组

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;

const int N = 300000 + 10;
typedef struct Node {
	int left,right,mid;
	int sum,cnt;
};

Node tree[N];

void build_Tree(int left,int right,int root) {
	tree[root].left = left;
	tree[root].right = right;
	tree[root].mid = (left + right)/2;
	tree[root].sum = 0;
	if(left == right)return;
	build_Tree(left,tree[root].mid,2 * root);
	build_Tree(tree[root].mid + 1,right, 2 * root + 1);
}

void update(int left,int right,int root) {
	if(tree[root].left == tree[root].right) {
		tree[root].sum++;
		return;
	}
	if(left > tree[root].mid)
		update(left,right,2 * root + 1);
	else if(right <= tree[root].mid)
		update(left,right,2 * root);
	else {
		update(left,tree[root].mid,2 * root);
		update(tree[root].mid + 1,right,2 * root + 1);
	}
}

int ans;

void find(int pos,int root) {
	ans += tree[root].sum;
	if(tree[root].left == tree[root].right && tree[root].left == pos)return;
	if(pos <= tree[root].mid)
		find(pos,2 * root);
	else 
		find(pos,2 * root + 1);
}

int main() {
	int n;
	int x,y;
	while(scanf("%d",&n),n) {
		build_Tree(1,n,1);
		for(int i=0;i<n;i++) {
			scanf("%d %d",&x,&y);
			update(x,y,1);
		}
		for(int i=1;i<n;i++) {
			ans = 0;
			find(i,1);
			printf("%d ",ans);
		}
		ans = 0;
		find(n,1);
		printf("%d\n",ans);
	}
	return 0;
}

树状数组的，那就是先成段更新 再查找某一点的值了 

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;

const int N = 100000 + 10;

int c[N];
int n;

void clear() {
    memset(c,0,sizeof(c));
}

int lowbit(int x) {
    return x&(-x);
}
//设原始矩阵为a,将a[i]加上val时对c所做的修改
void update(int i, int val) {
    while (i <= n) {
        c[i]+=val;
        i += lowbit(i);
    }
} 
//求前i项元素的和
int get_sum(int i) {
    int sum=0;
    while (i > 0) {
        sum += c[i];
        i -= lowbit(i);
    }
    return sum;
}

int main() {
    int x,y;
    while(scanf("%d",&n),n) {
        clear();
        for(int i=0;i<n;i++) {
            scanf("%d %d",&x,&y);
            update(x,1);
            update(y+1,-1);
        }
        for(int i=1;i<n;i++)
            printf("%d ",get_sum(i));
        printf("%d\n",get_sum(n));
    } 
    return 0;
}

HDU1556 Color the ball 树状数组 修改区间值 查找单点值,布布扣,bubuko.com

HDU1556 Color the ball 树状数组 修改区间值 查找单点值

原文：http://blog.csdn.net/yitiaodacaidog/article/details/24270351