树状数组

插入 查询 $logn$
一个极其优美的数据结构
完美地解决前缀和的相关问题
相比于线段树有一定的局限性

可以解决什么

• 单点修改 区间查询
• 区间修改 单点查询
• 区间修改 区间查询

lowbit

int lowbit(int x){
	return x&(-x);
}

简而言之，巧妙地截取十进制数下二进制地最末1至结尾地部分

• 如
• 十进制--------二进制
• 156-----------10011100
• 截取了末尾的100

updata

void updata(int i,int x){
	while(i<=n){
		c[i]+=x;
		i+=lowbit(i);
	}
	return ;
}

将当前所有包含该节点的节点都加上变化的i值

getsum

int getsum(int x){
	int sum=0;
	while(x>0){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}

将下标前缀相加

单点修改 区间查询

一开始默认建立一个全为零的数列
每加入一个数，就相当于单点修改updata(i,a[i])
单点修改 +x
单点替换 -a[i]+x;
区间查询 （l,r） getsum(r)-getsum(l-1)

区间修改 单点查询

由于时间复杂度的限制不可能$O(n)$单点修改
此时需要一个奇妙的思想 差分
构建一个新的序列$\{b[i] \}$，在此序列上建立树状数组
将$a[i]-a[i-1]$作为$b[i]$存入树状数组中
单点查询 $getsum(i)$
区间修改 $(l,r)$ 加上x
$updata(l,x),updata(r+1,-x)$

区间修改 区间查询

我们在差分的思想上进行区间查询的操作
区间查询$(l,r)$ 考虑$sum(r)-sum(l-1)$
$s=sum(r)-sum(l-1)$
$a[i]=b[1]+b[2]+b[3]+....+b[i]$
$sum(i)=a[1]+a[2]+a[3]+...+a[i]$
$sum(i)=i\times b[1]+(i-1)\times b[2]+(i-3)\times b[3]+...+b[i]$
$sum(i)=i\times(a[i])-(i-1)\times b[i]-(i-2)\times a[i-1]-...-1\times b[2]-0\times b[1]$
由此看出维护一个$(n-1)\times b[n]$的树状数组${c2[i]}$即可
$sum(i)=n\times sum(b[i])-sum(c2[i])=sum(n\times b[i]-c2[i])$
$\{c1[i]\}$存差分$\{b[i]\}$数组
{c2[i]} 存$(i-1)\times b[i]$数组

void updata(int i,int k){
	int x=i;
	while(i<=n){
		c1[i]+=k;
		c2[i]+=k*(x-1);
		i+=lowbit(i); 
	}
	return ;
}

int getsum(int i){
	int x=i;
	int sum=0;
	while(i){
		sum+=x*c1[i]-c2[i];
		i-=lowbit(i);
	}
	return sum;
}

**区间修改 区间查询 模板

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[100001];
int c1[100001];
int c2[100001];
int lowbit(int i){ return i&(-i);}
void updata(int i,int k){
	int x=i;
	while(i<=n){
		c1[i]+=k;
		c2[i]+=k*(x-1);
		i+=lowbit(i); 
	}
	return ;
}
int getone(int i){
	int sum=0;
	while(i){
		sum+=c1[i];
		i-=lowbit(i);
	}
	return sum;
}
int getsum(int i){
	int x=i;
	int sum=0;
	while(i){
		sum+=x*c1[i]-c2[i];
		i-=lowbit(i);
	}
	return sum;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		updata(i,a[i]-a[i-1]);
	}
	for(int i=1;i<=n;++i){
		cout<<getone(i)<<' ';
	}
	cout<<endl;
	for(int i=1;i<=n;++i){
		for(int j=i;j<=n;++j){
			cout<<i<<' '<<j<<' '<<getsum(j)-getsum(i-1)<<endl; 
		}
	}
	updata(1,1);
	updata(n+1,-1);
	for(int i=1;i<=n;++i){
		cout<<getone(i)<<' ';
	}
	cout<<endl;
	for(int i=1;i<=n;++i){
		for(int j=i;j<=n;++j){
			cout<<i<<' '<<j<<' '<<getsum(j)-getsum(i-1)<<endl;
		}
	}
	return 0;
}
/*
8 
1 1 1 1 1 1 1 1 
*/