树状数组的原理和实现
树状数组的原理和实现
分类:
IT文章
•
2022-05-01 10:38:00
其中a数组就是原数组，c数组则是树状数组，可以发现
C1 = A1
C2 = A1+A2
C3 = A3
C4 = A1+A2+A3+A4
C5 = A5
C6 = A5+A6
C7 = A7
C8 = A1+A2+A3+A4+A5+A6+A7+A8
注意：LOWBIT无法处理0的情况，因为它的结果也是0，那么最终就是一个死循环
):
if x < 1:
return
while x <= n:
fenwick[x] += delta
x += LOWBIT(x)
):
result = 0
while right > 0:
result += fenwick[x]
x -= LOWBIT(x)
return result
例如
15=(1111)2，通过lowbit分解，它可以变成4个数的和：
所以C(15) = C(14) + C(12) + C(8) + C(0)，由图也可以得知，其结果是正确的。
除此之外，树状数组能够快速的求任意区间的和，设sum(k) = A[1] + A[2] + ... + A[k]，则A[i] + A[i+1] + ... + A[j] = sum(j) - sum(i-1)。
#include<string.h>
int c[32000+10];
int a[15000+10];
int lowbit(int x)
{
return x&(-x);
}
void updata(int x,int d)
{
while(x<=32001)
{
c[x]=c[x]+d;
x=x+lowbit(x);
}
}
int getsum(int x)
{
int res = 0;
while(x>0)
{
res=res+c[x];
x=x-lowbit(x);
}
return res;
}
int main()
{
int n;
int i,x,y;
while(scanf("%d",&n)!=EOF)
{
memset(c,0,sizeof(c));
memset(a,0,sizeof(a));
for(i=0; i<n; i++)
{
//因为y是升序,所以横坐标小于x的，（想了很久）所有点都符合,这是解这道题的关键。
scanf("%d%d",&x,&y); //下标可能从0开始，所以要x+1
a[getsum(x+1)]++; //求出横坐标小于x的所有stars个数，并记录到a中
updata(x+1,1); //更新区间
}
for(i=0; i<n; i++)
{
printf("%d
",a[i]);
}
}
return 0;
}
