POJ3321——树状数组_POJ树状数组初探

本文主要是介绍POJ3321——树状数组_POJ树状数组初探，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文出自：http://blog.csdn.net/svitter

树状数组用于处理求区间内的值和改变单个元素的值，要注意树状数组从数组下标1开始。

基础算法：

获取全部的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));

题目：POJ3321

题意：一颗苹果树，树上有多个苹果，一个分支一个苹果，求一个节点以上苹果的个数。操作有添加和删除苹果。（如果原本有苹果，则添加，没有则删除。一开始全部有苹果）。

测试数据：第一行为一个n，代表分支个数。随后输入分支关系。（邻接表）第二行为一个m，代表操作个数。随后输入Q或者C加一个数字，代表求和或者对树进行删除或者添加操作。

思路：考虑是稀疏图使用邻接表存存储。STL_稀疏图，树_使用vector邻接表存储。求段间和，只改变其中一个元素，可以使用树状数组。以根为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 求出最后结果（除了选择节点的苹果，其他的苹果都走了两遍）。

C: 更改与树状数组的modify结合，更改apple节点。Query函数求出的不是苹果的值。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>using namespace std;#define MY_MAX 220000typedef 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 mapfor(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\n", (t1-t2)/2);}}return 0;
}

这篇关于POJ3321——树状数组_POJ树状数组初探的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---