树状数组_树状数组的时间复杂度

1.平常我们会遇到一些对数组进行维护查询的操作，比较常见的如，
①修改某点的值
②求某个区间的和


2.当数据规模不大的时候，
①对于修改某点的值是非常容易的，时间复杂度为 O(1)
②求一个区间和就要从start循环到end，时间复杂度为 O(n)
③如果实时的对数组进行 M次修改或求和，最坏的情况下
时间复杂度为 O(M*N),当规模增大后，必定超时

3.树状数组的时间复杂度为 O(M*logN)  

4. A数组就是我们要维护和查询的数组，其实整个过程中根本用不到，
C数组才是重点，C数组的构造规则为： 
C8=C4+C6+C7+A8,C6=C5+A6,C4=C2+C3+A4,C2=C1+A2...
C8表示 A1~A8的和，C6表示 A5~A6的和， 
C8可以看做左半边的和 A1~A4 + 右半边的和 A5~A8，
左半边的和确定为 C4，右半边同样的规则把A5~A8一分为二，
继续下去都是一分为二，直到不能再分

5.树状数组的基础就是一个被构造出来的式子：c[i]=a[i]+a[i-1]+...+a[i-2^k+1];

k代表二进制的最后连续 0的个数,   比如，对于1000和101000，k=3

6.lowbit(k)就是把 k的二进制的高位1全部清空，只留下最低位的 1，
比如,10的二进制数是1010，则lowbit(10)=lowbit(1010)=0010;


7.实现方法 lowbit(k)=k&-k,
一个数加一个负号就是把这个数的二进制取反加一 
如 -10的二进制就是 -1010=0101+1=0110，然后 1010 & 0110=0010
 
8.节点与其子树的关系，i=j+lowbit(j),lowbit是 j的最低位 1所代表

的数字，可以把子区间的变化以 log 2n的次数传递上去 

int lowbit(int i)
{
	return i&(-i);
 } 
void add(int i,int value)
{
	while(i<=N){
		c[i]+=value;
		i+=lowbit(i);
	}
}
int sum(int i){
	int sum=0;
	while(i>0){
		sum+=c[i];
		i-=lowbit(i);
	}
	return sum;
}

总结：

树状数组(Binary Indexed Tree)

1.解决动态前缀和问题的数据结构

2.查询区间和,例如区间和[5,8]=sum(8)-sum(4); 

3.解决区间加/单点查询问题 
例如：给区间[3,6]所有元素加一个数5，
执行的操作是add(3,5),add(6+1,-5); 
然后查询3,4,5,6点的值，比原来大5
 
4.二维树状数组
单点修改+二维前缀和sum(x,y)（即子矩阵元素之和） 

例题：
poj2352 二维偏序问题
bzoj 1878,2743,1452
Codeforces Round #755D
题解：

www.cnblogs.com/autsky-jadek/ 

const int maxn=305;
struct BIT_2D{
	int d[maxn][maxn];
	void update(int x,const int &y,const int &v){
		for(;x<=n;x+=(x&(-x)))
		for(int j=y;j<=n;j+=(j&(-j)))
		d[x][j]+=v;
	}
	int getsum(int x,const int &y)
	{
		int res=0;
		for(;x;x-=(x&(-x)))
		for(int j=y;j;j-=(j&(-j)))
		res+=d[x][j];
		return res;
	}
}; 

模板题目：HDU 1166  

点击打开链接

#include<bits/stdc++.h>
using namespace std;
int N,c[50005];
int lowbit(int i)
{
	return i&(-i);
 } 
void add(int i,int value)
{
	while(i<=N){
		c[i]+=value;
		i+=lowbit(i);
	}
}
int sum(int i){
	int sum=0;
	while(i>0){
		sum+=c[i];
		i-=lowbit(i);
	}
	return sum;
}
int main()
{
	int t,kase=1,d;
	scanf("%d",&t);
	while(t--)
	{
		printf("Case %d:\n",kase++);
		scanf("%d",&N);
		memset(c,0,sizeof(c));
		for(int i=1;i<=N;i++){
			scanf("%d",&d);
			add(i,d);
		}
		char command[15];int a,b;
		while(~scanf("%s",command)&&command[0]!='E'){
			//getchar(); 
			
			scanf("%d%d",&a,&b);
			if(command[0]=='Q')
			//c[1]~c[b]的和为sum(b),c[1]~c[a-1]的和为sum(a-1)
			//c[a]~c[b]的和为sum(b)-sum(a-1) 
				printf("%d\n",sum(b)-sum(a-1));
			if(command[0]=='A')
			add(a,b);
			if(command[0]=='S')
			add(a,-b);
		}
	}
	return 0;
}

例一：bzoj1878

点击打开链接

1878: [SDOI2009]HH的项链

Time Limit: 4 Sec   Memory Limit: 64 MB
Submit: 5674   Solved: 2807
[ Submit][ Status][ Discuss]

Description

Input

Output

Sample Input

Sample Output

题意：
给一个n个数的序列，m个询问，每次询问一个区间内不同的数的个数 


思路：
每个数都可以预处理它上一次出现在什么位置，
每次添加元素的时候，将它上一次出现的位置+1的地方加1，
然后在其本身位置+1的值打上个-1标记，这样就成了线性求值，
也就是每次求getsum(a[i].l)。


所有区间按右端点排序 对于每一个[l,r]可以这样处理： 

l~r中的数的上一次出现的位置在l左边的数的个数

#include <stdio.h>
#include <algorithm>
using namespace std ;
struct node
{
    int l ;
    int r ;
    int id ;
};
node a[200100] ;
int pre[200100] ;
int col[200100] ;
int c[200100] ;
int ans[200100] ;
int last[1000100] ;
int n;
int lowbit(int x)
{
    return x&(-x) ;
}
void update(int x , int p)
{
    while(x <= n)
    {
        c[x] += p ;
        x += lowbit(x) ;
    }
}
int getsum(int x)
{
    int sum = 0 ;
    while(x)
    {
        sum += c[x] ;
        x -= lowbit(x) ;
    }
    return sum ;
}
int cmp(node asdf, node b)
{
    return asdf.r < b.r;
}
int main()
{
    scanf("%d" , &n) ;
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d" , &col[i]) ;
        pre[i] = last[col[i]] ;
        last[col[i]] = i ;
    }
    int m ;
    scanf("%d" , &m) ;
    for(int i = 1 ; i <= m ;i++)
    {
        scanf("%d%d" , &a[i].l , &a[i].r) ;
        a[i].id = i ;
    }
    sort(a + 1 , a + 1 + m , cmp) ;
    int now = 0 ;
    for(int i = 1 ; i <= m ; i++)
    {
        while(now < a[i].r)
        {
            now ++ ;
            update(pre[now] + 1 , 1) ;
            if(now != n){update(now + 1 ,-1) ;}
        }
        ans[a[i].id] = getsum(a[i].l) ;
    }
    for(int i = 1 ; i <= m ; i++)
    {
        printf("%d\n" , ans[i]) ;
    }
}

poj2352 Stars 树状数组 
题意： 
给出N个星星的坐标(包括0)，已经先按y递增，若y相等，x递增排序，
每个星星都有一个等级，规定它的等级就是在它左下方的星星的个数
依次输出0到n-1的星星的个数


思路：
树状数组最基本的应用，统计横坐标为x的星星前面比它小的星星的个数
注意：

1.树状数组下标为0的位置不可用，所以在输入坐标时加1 

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
 
#define CLR(arr, val) memset(arr, val, sizeof(arr))
#define N 32010//0<=X,Y<=32000
 
int n;
int lev[N], c[N];
 
int lowbit(int x)
{
	return x & (-x);
}
 
void add(int i, int data)
{
	while(i < N)//这里应该特别注意，是x的范围，而不是数据量n 
	{
		c[i] += data;
		i += lowbit(i);
	}
}
 
int getsum(int x)
{
	int res = 0;
	while(x > 0)
	{
		res += c[x];
		x -= lowbit(x);
	}
	return res;
}
 
int main()
{
	int x, y;
	while(~scanf("%d", &n))
	{
		CLR(lev, 0); CLR(c, 0);
		for(int i = 0; i < n; ++i)
		{
			scanf("%d%d", &x, &y);
			x++; //有0出现，树状数组无法处理。故+1
			lev[getsum(x)]++; //先统计，不包括本身
			add(x, 1); //加入
		}
		for(int i = 0; i < n; ++i)
			printf("%d\n", lev[i]);
	}
	return 0;
}