树状数组

例题

给定一个长度为$n$数组，两个操作（n<=1e5） 1.将一个位置的值加一 2.找到l-r区间的和

按常理来向，我们会用前缀和或差分来维护，但...

如表所示

	改	找
前缀和	O(n)	O(1)
差分	O(1)	O(n)

都会超时

所以我们要用树状数组来解决问题

首先我们先用lowbit来构建一个数组 (lowbit多少他就管i~i+lowbit(i)-1)

rt

说明

lowbit(i)=i&-i

举例

图中的c1管的范围是1~1

c6是6~7(lowbit(6)==2)

c16是1~16(lowbit(16)==16)

查找

11-lowbit(11)=10

10-lowbit(10)=8

如果把路径上的这些值都加起来，就是$1-i$的和（前缀和$1-i$）

改动

9+lowbit(9)=10

10+lowbit(10)=12

12+lowbit(12)=16

如果把路径上的这些数多加上改动的值

这样就可以实现一个动态前缀和的改动(如果不理解请看一下查找并带入几个数据算一下)

时间复杂度是O(log n)

模版

void add(int v,int x){
	for(int i=v;i<=n;i+=(i&-i))c[i]+=x;
}
int cx(int x){
	int res=0;
	for(int i=x;i;i-=(i&-i))res+=c[i];
	return res;
}

T1 楼兰图腾

思路

对于一个点，^就是左边比他小的乘右边比他小的，v就是左边比他大的成右边比他大的

考虑一下暴力，我们可以遍历整个数组，用桶记录求出每个值当前出现的次数，然后遍历>a[i]和<a[i]的部分求出和并记录,最后再相乘（左边>a[i]*右边>a[i] 左边<a[i]*右边<a[i]）求出答案

我们发现维护桶数组和求和的这一个部分可以看成一个动态前缀和（求一个范围那块就可以用前缀和，但有改动,所以要动态前缀合），所以就能用树状数组优化

T2一个简单的整数问题

其实不怎么简单

思路

这题的难点在于怎么把树状数组变成改区间差单点

不过我们可以发现的是 树状数组是加入原数组，维护成前缀和，而我们加入差分数组，就可以维护成原数组

并且根据差分的性质我们可以改变一个区间的量

查找时一层一层加上值也可以算出那个输的原值

T3一个简单的整数问题

真的不简单

思路

我们先列个数组 b:差分数组 而要求1~n所有的数的和时 也就是:

$$S_n=\sum\limits_{i=1}^n\sum\limits_{j=1}^ib_j$$

还是图中全部分减去蓝色

大正方形的和：

$$(n+1)\sum\limits_{i=1}^nb_i$$

蓝色部分的和：

$$a_1+a_2+a_3+...+a_n$$

化简为：

$$\sum\limits_{i=1}^ni \times b_i$$

所以：

$$S_n=\sum\limits_{i=1}^n(n-i+1)b_i=(n+1)\sum\limits_{i=1}^nb_i-\sum\limits_{i=1}^ni \times b_i$$

所以我们就可以用两个树状数组，一个维护$b_i$，一个维护$i\times b_i$

区间查询:

        int su1=(r+1)*cx(a,r)-cx(b,r);//1~r的前缀和
		int su2=(l)*cx(a,l-1)-cx(b,l-1)//1~(l-1)的前缀和
		cout<<su1-su2<<"\n";

区间更改

        add(a,l,d);
  	    add(a,r+1,-d);//b[i]的前缀和
		add(b,l,l*d);
		add(b,r+1,(r+1)*-d);//i*b[i]的前缀和

T4 Lost Cows

思路

我们发现，如果我们从后往前遍历，其实前面有多少头牛小于他的身高($a_i$)就相当于他是所有剩余身高中的第$a_i+1$小

所以我们用树状数组来表示剩余身高（1代表还有,0代表被选了）

然后用二分找到前面有$a_i+1$个一的位置，并减去当那个位置，并记录在答案数组

最后输出

T5 Buy Tickets

思路

我们发现，如果我们从后往前遍历，其实他插队是第几个就相当于他是所有剩余位置中的第$a_i+1$小

所以我们用树状数组来表示剩余位置（1代表还有,0代表被选了）

然后用二分找到前面有$a_i+1$个一的位置，并减去当那个位置，并记录在答案数

相对于第四题改个输入输出就行了