程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3321 Apple Tree（樹狀數組）

poj 3321 Apple Tree（樹狀數組）

編輯：C++入門知識

poj 3321 Apple Tree（樹狀數組）

輝煌北大的月賽題質量真高啊，這種樹狀數組真難想到。

樹狀數組的基本用法是區間，單點的應用，起初這個怎麼都想不到如何套用到樹狀數組。

轉化方法是將樹上的節點信息查詢，轉為深度優先中節點順序（代表結點編號）。進結點與出結點分別代表該結點管轄范圍。

題目大意級是說，給你一顆樹，最初每個節點上都有一個蘋果，有兩種操作：修改（即修改某一個節點，修改時這一個節點蘋果從有到無，或從無到有）和查詢（查詢某一個節點他的子樹上有多少個蘋果）。

由於此題數據比較大(N<=10^5)，而且不是標准的二叉樹，所以這裡我們隊每一個節點重新編號，另外為每一個節點賦一個左值和一個右值，表示這個節點的管轄范圍。

也就是DFS搜索的時候做標記的過程，這樣新的編號為1~6的節點所管轄的范圍分別就是[1,6] [2,4] [3,3] [4,4] [5,6] [6,6]，其中左邊的是左值，右邊的是右值，節點1的區間是[1,6]，正好這棵子樹有6個節點，其他也一樣

#include
#include 
#include
#include
#include 
#include
#include
using namespace std;
#define N 100010
int n,m;


int lowbit(int x){return -x&x;}
void update(int *arr,int r,int num)
{
	int i;
	for(i=r;i<=n;i+=lowbit(i))
		arr[i]+=num;

}
int getsum(int *arr,int r)
{
	int i;
	int ans=0;
	for(i=r;i>0;i-=lowbit(i))
		ans+=arr[i];
	return ans;
}

int head[N];
int next[N];
int netb[N];
int deh1[N];
int deh2[N];
int cnt,depth;
int arr[N];
int a[N];
void init()
{
	int i;
	//memset(a,0,sizeof(a));
	memset(deh1,0,sizeof(deh1));
	memset(head,-1,sizeof(head));
	cnt=0;depth=0;
	for(i=1;i<=n;i++)
		update(arr,i,1),a[i]=1;

}
void add(int u,int v)
{
	netb[cnt]=v;next[cnt]=head[u];head[u]=cnt++;
}
void dfs(int u)
{
	deh1[u]=++depth;//代表左
	int i;
	for(i=head[u];~i;i=next[i])
	{
		int v=netb[i];
			dfs(v);
	}
	deh2[u]=depth;//代表右
}
int main()
{
	int i,j,k,u,v,m;
	char str[10];
	while(~scanf("%d",&n))
	{
		init();
		for(i=1;i