树状数组:主要是一维
当然也需要学习二维的树状数组，可以看看二维树状数组
模板：
取数组下标二进制非0最低位所表示的值；
单点更新；
区间查询。
单点更新：
树状数组可以以nlogn的时间复杂度求序列的逆序对；
比如图：
我们要更新c[4]的值，那么，我们只要更新，c[1]及c[3],当c[1]改变那么c[2]也随之改变，如此类推；
c[3],的值；
它们的更新过程，其实是查询过程的逆过程，也就是向下更新，由叶子结点向上更新c[]数组；
sum[4]=A[1]+A[2]+A[3]+A[4]；
int lowbit(int x)//
{
return x&(-x);
}
void update(int x,int val)//更新的值为val
{
for(int j=x;j<=n;j+=lowbit(j))
{
c[j]+=val;
}
}
每次查询是求从查询节点开始（包括查询节点）自右向左层数尽可能低的点的权值的和，算过的点的根节点不再计算（也就是从查询节点开始，从右到左所有需要计算的点的权值和），得到的是前缀和。
每次修改是修改以该点为子节点的所有节点的值。
查询和修改都是以跳跃的形式进行的，时间复杂度都为logn。
比如这个图：
我们进行向上区间查询（求和）
我们进行区间查询（求和）：利用C[i]数组，求A数组中前i项和：
比如：
i=7，前7项和：sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]；
而C[4]=A[1]+A[2]+A[3]+A[4]；
C[6]=A[5]+A[6]；
C[7]=A[7]；
可以得到：sum[7]=C[4]+C[6]+C[7]。
数组下标写成二进制：sum[(111)]=C[(100)]+C[(110)]+C[(111)]；
int lowbit(int x)//
{
return x&(-x);
}
int sum(int k)//求和
{
int ans=0;
for(int i=k;i>0;i-=lowbit(i))
{
ans+=c[i];//
}
return ans;
}
由于课程关系
简单写了一点理解：
参考文献
可以看道题；
题目链接
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 500010
#define ll long long
int c[MAX];
int num[MAX];
int n;
int lowbit(int x)// **取数组下标二进制非0最低位所表示的值；**
{
return x&(-x);
}
//void update(int x,int val)//修改
//{
// while(x<=n){
// c[x]+=val;
// x+=lowbit(x);
// }
//}
//update(a[i],1);
void update(int x) **单点更新；**//传参 +in val
{
while(x<=MAX)
{
c[x]++;//val变为1；//val 为其它
x+=lowbit(x);
}
}
void update(int x)//修改
{
for(int j=x; j<=; j+=lowbit(j))
{
c[j]++;
}
}
int sum(int k)//求和 **区间查询。**
{
int ans=0;
for(int i=k; i>0; i-=lowbit(i))
{
ans+=c[i];
}
return ans;
}
int sum(int x)//节点 求值
{
int s=0;
while(x)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
bool cmp(node a,node b){//排序
return a.val<b.val;
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
int x,y;
memset(c,0,sizeof(c));
memset(num,0,sizeof(num));
for(int i=1; i<=n; i++)
{
scanf("%d%d",&x,&y);
x++;//
num[sum(x)]++;
update(x);
}
for(int i=0; i<n; i++)
printf("%d\n",num[i]);
}
return 0;
}
最后说一下树状数组的优缺点：
①特点：代码短小，实现简单；容易扩展到高纬度的数据；
②缺点：只能用于求和，不能求最大/小值；不能动态插入；数据多时，空间压力大。
京公网安备 11010502036488号