那么,何为树形数组呢??
下图中的C数组就是树状数组,a数组是原数组;
![]()
可以发现这些规律:
C1=a1
C2=a1+a2
C3=a3
C4=a1+a2+a3+a4
C5=a5
……
C8=a1+a2+a3+a4+a5+a6+a7+a8
……
C2^n=a1+a2+….+a2^n
对于序列a，我们设一个数组C定义C[t] = a[t – 2^k + 1] + … + a[t]，k为t在二进制下末尾0的个数。
K的计算可以这样:
2^k=t and (t xor (t-1))
以6为例
(6)10=(0110)2
xor 6-1=(5)10=(0101)2
(0011)2
and (6)10=(0110)2
(0010)2
所以问题变的很简单,重要写几个函数就可以了;
求2^k的函数代码如下:
int Lowbit(int t)
{
return t & ( t ^ ( t - 1 ) );
}
|
求1 -- end和的函数代码如下:
int Sum(int end)
{
int sum = 0;
while(end > 0)
{
sum += in[end];
end -= Lowbit(end);
}
return sum;
}
|
对某位进行操作函数如下(以加法为例)
void plus(int pos , int num)
{
while(pos <= n)
{
in[pos] += num;
pos += Lowbit(pos);
}
}
|
有了这三个函数整个树形数组也就基本构建成功啦!!
对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度有3N降为N,时间效率也有所提高.编程复杂度更是降了不少.
下面是用树状数组做的 pku star
#include <iostream>
using namespace std;
const int N = 32100;
int c[N];//树状数组
int lowBit(int x) 
{
return x & (x ^ (x - 1));
}
void add(int x, int k) {
//a[x] += k
while (x <= N) {
c[x] += k;
x += lowBit(x);
}
}
void sub(int x, int k) {
//a[x] -= k
while (x <= N) {
c[x] -= k;
x += lowBit(x);
}
}
int sum(int x) {
//return sum(1..x);
int ret = 0;
while (x > 0) {
ret += c[x];
x -= lowBit(x);
}
return ret;
}
int out[N];
int f[N];
int main() {
//pku2352
int i, j, k, x, y;
int n;
scanf("%d", &n);
for (i=0; i<n; i++) {
scanf("%d%d", &x, &y);
x++;
add(x,1);
out[sum(x-1) + f[x]]++;
f[x]++;
}
for (i=0; i<n; i++) {
printf("%d\n", out[i]);
}
system("pause");
return 0;
}posted on 2007-03-01 22:02
豪 阅读(1577)
评论(3) 编辑 收藏 引用 所属分类:
数据结构与算法