POJ 3321——樹状配列_POJツリー配列の初探

本論文の出典:http://blog.csdn.net/svitter
ツリー配列は、求める区間内の値を処理し、単一の要素の値を変更するために用いられます.ツリー配列は、配列の下から始まることに注意してください.
基礎アルゴリズム:
全部のlowbit値を取得し、重複計算を防止します.

void getLowbit()
{
    for(int i = 0; i < 1000; i++)
        lowbit[i] = i & (-i);
}

区間と1~iを求めます

int Sum(int i)
{
    int sum = 0;
    while(i > 0)
    {
        sum += C[i];
        i = i - lowbit[i];
    }
    return sum;
}

要素iの値を変更します.

void Change(int i, int inc)
{
	while(i <= n)
	{
		C[i] += inc;
		i = i + lowbit[i];
	}
}

Cnの求め方:

sum(n) - sum(n - lowbit(n));

タイトル:POJ 3321
一つのリンゴの木には複数のリンゴがあり、一つの分岐点に一つのリンゴがあり、一つのノード以上のりんごの個数を求めます.操作はアップルの追加と削除があります.(本来はリンゴがあれば追加し、なければ削除します.最初は全部リンゴがあります.)
テストデータ:第一挙動nは分岐個数を表します.その後、分岐関係を入力します.(隣接表)第二行為の一mは、操作個数を表します.次にQまたはCを入力して数字を加え、合計またはツリーを削除または追加する操作を表します.
考え:間引き図は隣接表を用いて保存することを考える.STL_間引き図vector隣接表を使って保存します.セグメント間の和を求めて、その中の1つの要素だけを変えて、木の形の配列を使うことができます.根を1とし、上ノードを別の側とする.深検索を使ってリンゴの数を統計します.
C[i]はSum(i)-Sum(i-lowbit[i])でi-(i-lowbit[i])です.C[time]
Q:start[n]とend[n]を使ってアクセス時間を記憶し、(end[n]-start[n]+1)/2を使って最終結果を求める(選択ノードのリンゴを除いて、他のリンゴは全部2回行った).
C:ツリー配列のmodifyと結合して、appleノードを変更します.Query関数が求めているのはリンゴの値ではありません.

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define MY_MAX 220000

typedef vector<int> VCT_INT;
vector <VCT_INT> G(MY_MAX/2);


int C[MY_MAX];
int lowbit[MY_MAX];

bool HasApple[MY_MAX];

int start[MY_MAX];
int end[MY_MAX];
int nCount = 0;

void DFS(int v)
{
    start[v] = ++ nCount;
    for(int i = 0; i < G[v].size(); i++)
        DFS(G[v][i]);
    end[v] = ++ nCount;
}


int QuerySum(int p)
{
    int nSum = 0;
    while(p > 0)
    {
        nSum += C[p];
        p -= lowbit[p];
    }
    return nSum;
}

void Modify(int p, int val)
{
    while(p <= nCount)
    {
        C[p] += val;
        p += lowbit[p];
    }
}

void getLowbit()
{
    for(int i = 1; i < MY_MAX; i++)
        lowbit[i] = i & (-i);
}


int main()
{
    int n, m;
    scanf("%d", &n);
    int x, y, i, j ,k;
    int a, b;
    getLowbit();
    //build map
    for(i = 0; i < n - 1; i++)
    {
        scanf("%d%d", &a, &b); 
        G[a].push_back(b); 
    } 
    nCount = 0; DFS(1); 
    for(i = 1; i <= n; i++)
        HasApple[i] = 1;

    for(i = 1; i <= nCount; i++)
        C[i] = i - (i - lowbit[i]);

    scanf("%d", &m);

    while(m--)
    {
        char cmd[10];
        scanf("%s%d", cmd, &a);
        if(cmd[0]== 'C')
        {    if(HasApple[a])
            {
                Modify(start[a], -1);
                Modify(end[a], -1);
                HasApple[a] = 0;
            }
            else
            {
                Modify(start[a], 1);
                Modify(end[a], 1);
                HasApple[a] = 1;
            }
        }
        else
        {
            int t1 = QuerySum(end[a]);
            int t2 = QuerySum(start[a]-1);
            printf("%d
", (t1-t2)/2);
        }
    }

    return 0;
}