树状数组的学习

Binary Indexed Tree, 树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。
用于解决动态前缀和的[[数据结构]]，涉及区间问题

事实上，树状数组能解决的问题是[[线段树]]能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小

我们总能将一段前缀[1, n]拆成 不多于logn段区间，使得这 logn 段区间的信息是 已知的。

区间查询

查询复杂度 O(logn) （每次抹掉二进制最后一个1）
查询这个节点管辖的区间
设节点编号为x，那么这个节点管辖的区间为 2^k 个元素，（其中k为二进制末尾0的个数）
因为这个区间的最后一个元素必然为Ax

事实上，将有关[l, r]的区间询问转化为[1, r] 和 [1, l-1] 的前缀询问再差分，在竞赛中是一个非常常用的技巧。

int getsum(int x) { // a[1]..a[x]的和 
	int ans = 0; 
	while (x > 0) { 
		ans = ans + c[x]; 
		x = x - lowbit(x); 
	} 
	return ans; 
}

单点修改

修改相当于查询，是一个逆的过程
我们的目标是快速正确地维护 c 数组。为保证效率，我们只需遍历并修改管辖了a[x]的所有c[y]，因为其他的  显然没有发生变化。

void add(int x, int k) { 
	while (x <= n) { // 不能越界 
		c[x] = c[x] + k; 
		x = x + lowbit(x); // 往上(后)跳
	}
}

lowbit函数

返回某个数二进制末尾的1的位置
注：负数在二进制使用补码的方式储存，即反转bit然后+1

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

建树

也就是根据最开始给出的序列，将树状数组建出来（c 全部预s处理好）。
一般可以直接转化为 n 次单点修改，时间复杂度 (n log n)。
比如给定序列 a = (5, 1, 4) 要求建树，直接看作对 a[1] 单点加 5，对 a[2] 单点加 1，对 a[3] 单点加 4 即可。 (注意这里下标从1 开始)

![[c20de385208081bade1c094229f692f.jpg]]

区间修改+单点查询

1. 新建数组a和d，a是数值，d是树状数组维护的 差分数组
2. 设l，r，v。每次进行区间修改的时候，add(l, v)，add(r+1, -v) 相当于在lr区间中施加了v的影响
   1. （在l处开始影响，在r+1处结束影响）
3. 要查询修改过的点x：a[x] + query(x);，意思是原值加上v的"影响"
4. 差分数组做一次前缀和就得到了总影响

相当于普通差分数组，树状数组维护后的差分数组单点查询的时间复杂度是 O(logn)
而普通差分数组修改后再查询的时间复杂度是 O(n)

#区间问题