PS:未经许可，禁止转载。思路来源于我的老师 $\text{hoogy}$，非常感谢，%%%。
- 五分钟丝滑动画讲解 | 树状数组
-〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组
单点修改，区间查询
前置芝士：
一维前缀和
设原数组 $a$，前缀和数组 $b$，则有：$b[i]=\sum\limits_{j=1}^ia[j]$。
推导，得 $b[i]=b[i-1]+a[i]$。
___________
设原数组 $a$，树状数组 $b$，其中 $b[i]=\sum\limits_{j=i-lowbit(i)+1}^ia[j]$，即 $b[i]$ 表示的是结尾位置为 $i$，长度为$lowbit(i)$的前缀和数组的和。
修改时，每次 $i+=lowbit(i)$，找到包含位置 $i$ 的所有区间，将 $b[i]+=k$，其中 $k$ 为修改值。
询问时，每次 $i-=lowbit(i)$，将 $s+=b[i]$，即：
$s=\sum\limits_{j=i-lowbit(i)+1}^ia[j]+\sum\limits_{j=i-lowbit(i)-lowbit(i-lowbit(i))+1}^{i-lowbit(i)}a[j]+\sum\limits_{j=i-lowbit(i)-lowbit(i-lowbit(i))-lowbit(i-lowbit(i-lowbit(i)))+1}^{i-lowbit(i)-lowbit(i-lowbit(i))}a[j]...=\sum\limits_{j=1}^ia[j]$
__________________
区间修改，单点查询
前置芝士：
一维差分
设原数组 $a$，差分数组 $d$，则有：$\sum\limits_{j=1}^id[j]=a[i]$。
推导，得 $d[i]=a[i]-a[i-1]$。
____________________
设原数组 $a$，树状数组 $b$，差分数组 $d$，其中 $b[i]=\sum\limits_{j=i-lowbit(i)+1}^id[j]$，即 $b[i]$ 表示的是结尾位置为 $i$，长度为$lowbit(i)$的差分数组和。
修改区间 $[l,r]$ 时，需修改两个点 $l,r+1$，即 $add(l,k),add(r+1,-k)$，其中 $k$ 为修改值，每次 $i+=lowbit(i)$，找到包含位置 $i$ 的所有区间，将 $b[i]+=k$，其中 $k$ 为修改值。
询问时，每次 $i-=lowbit(i)$，将 $s+=b[i]$，即：
$s=\sum\limits_{j=i-lowbit(i)+1}^id[j]+\sum\limits_{j=i-lowbit(i)-lowbit(i-lowbit(i))+1}^{i-lowbit(i)}d[j]+\sum\limits_{j=i-lowbit(i)-lowbit(i-lowbit(i))-lowbit(i-lowbit(i-lowbit(i)))+1}^{i-lowbit(i)-lowbit(i-lowbit(i))}d[j]...=\sum\limits_{j=1}^id[j]=a[i]$
__________________
区间修改，区间查询
要求用树状数组进行区间修改，区间查询。
设原数组$A$。
设差分数组$D$，其中$\sum\limits_{j=1}^iD_j=a_i$。
则有
$\sum\limits_{i=1}^n{\sum\limits_{j=1}^iD_j}=\sum\limits_{i=1}^nA_i\Rightarrow \sum\limits_{i=1}^nD_i\cdot(n-i+1)=\sum\limits_{i=1}^nA_i\Rightarrow \sum\limits_{i=1}^nD_i\cdot n-\sum\limits_{i=1}^nD_i\cdot (i-1)=\sum\limits_{i=1}^nA_i\Rightarrow n\cdot\sum\limits_{i=1}^nD_i-\sum\limits_{i=1}^nD_i\cdot (i-1)=\sum\limits_{i=1}^nA_i$
其中设$C_i=D_i$，$E_i=D_i\cdot (i-1)$
用树状数组维护数组 $C$ 和 $E$。
对于每次修改：
若修改区间 $[l,r]$，将此区间加 $x$，则$add(l,x),add(r+1,-x)$。
在 $add$ 函数中，即 $add(x,y)$，必须将位置 $x$ 保留下来，这样才能每个区间加上的数字一样，例如 $int$ $k=x$，将 $x$ 保留，因为 $x$ 在后面会进行变化。
遍历编号为 $i$ 的后面一个区间，即每次 $i+=lowbit(i)$。
根据公式
$C_i=D_i$，$E_i=D_i\cdot (i-1)$
每次将$C_i+=y$，$E_i+=y\cdot (k-1)$。
对于每次查询：
若查询区间 $[l,r]$，则输出$ask(r)-ask(l-1)$。
在 $ask$ 函数中，即 $ask(x)$ ，必须将位置 $x$ 保留下来，理由同上。
遍历编号为 $i$ 的前面一个区间，即每次 $i-=lowbit(i)$。
根据公式
$n\cdot\sum\limits_{i=1}^nD_i-\sum\limits_{i=1}^nD_i\cdot (i-1)=\sum\limits_{i=1}^nA_i$
每次将$s+=x\cdot C_i-E_i$。
练习：
_____________________________
[P6225 [eJOI2019] 异或橙子](https://www.luogu.com.cn/problem/P6225)
求区间 $[l,r]$ 的所有子区间的异或和。
找规律：
对于区间 $[1,2]$，$a_1⊕a_2⊕(a_1⊕a_2)=(a_1⊕a_1)⊕(a_2⊕a_2)=0$
对于区间 $[1,3]$ 原式，$a_1⊕a_2⊕a_3⊕(a_1⊕a_2)⊕(a_2⊕a_3)⊕(a_1⊕a_2⊕a_3)=(a_1⊕a_1⊕a_1)⊕(a_2⊕a_2⊕a_2⊕a_2)⊕(a_3⊕a_3⊕a_3)=a_1⊕a_3$
规律：
若 $l,r$ 同奇偶，则有异或和 $a_l⊕a_{l+1}⊕a_{l+2}⊕...⊕a_{r-1}⊕a_{r}$；
若 $l,r$ 一奇一偶，则有异或和为 $0$。
用树状数组维护奇数数组和偶数数组即可。
________________
P2880 [USACO07JAN] Balanced Lineup G
用树状数组维护区间 $[l,r]$ 的最值。
其中，修改时，应修改位置 $x$ 的每一个所属区间，将每个含有位置 $x$ 的区间都与修改值 $y$ 比一遍最值即可，注意，此题部分题解不正确，虽然能过此题，但是如果边询问边修改会出问题。
PS:最大值与最小值求法差不多。
在求区间 $[l,r]$ 的最值时，应每次判断 $r-lowbit(r)$ 是否大于等于 $l$，即查询当前的区间 $[r-lowbit(r)+1,r]$ 是否跨越区间 $[l,r]$，由于 $maxn(minn)[r]$ 表示区间 $[l,r]$ 的最值。
- 若跨越区间 $[l,r]$ 可能求不到正确的最值，于是往前一个找，即取 $min(a[r-1],askmax(min)(l,r-1))$。
- 若不跨越区间，则取 $min(maxn(minn)[r],askmax(min)(l,r-lowbit(r)))$。
- 特殊情况：若 $l=r$，则其区间最值为 $a[r](a[l])$。
____________________________
P5094 [USACO04OPEN] MooFest G 加强版
将所有奶牛按 $v_i$ 排序，此时其位置 $x_i$ 乱了，用两个树状数组分别维护 $x_i$ 位置之前元素的个数以及 $x_i$ 位置之前的累加和，推出柿子即可。
P4145 上帝造题的七分钟 2 / 花神游历各国
一道有思维的树状数组。
树状数组很容易想到，但并查集却比较难想，因为一个很大的数开多次方都会变得很小，但其小于等于 $1$ 时，对其开方就没有用了，于是记录即可。
__________________________
二维树状数组
______________________
单点修改，区间求值。
前置芝士：
二维前缀和
设原数组 $a$，前缀和数组 $b$，则有：$b[i][j]=\sum\limits_{k=1}^i{\sum\limits_{l=1}^ja[k][l]}$。
推导，得 $b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]$。
_____________________________________
使用二维前缀和的思想即可。
______________________________
区间修改，单点求值。
前置芝士：
二维差分
设原数组 $a$，差分数组 $d$，则有：$\sum\limits_{k=1}^i{\sum\limits_{l=1}^jd[k][l]}=a[i][j]$。
推导，得 $d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$。
____________________________________________
使用查分思想，每次 $update(x_1,y_1,k),update(x_2+1,y_2+1),update(x_1,y_2+1,-k),update(x_2+1,y_1,-k)$，即可。
____________________________________________
P4054 [JSOI2009] 计数问题
二维树状数组维护其前缀和，其中 $C[i][j][c]$表示前 $i$ 行 $j$ 列的颜色为 $c$ 的格子的数量，即可。
求逆序对
前置芝士：
逆序对
设原数组 $a$， 若有一对数 $(a[i],a[j])$，当且仅当 $i<j$ 且 $a[i]>a[j]$，则成这对数为逆序对。
________________________
暴力思想：
正向求解
正向遍历，每次将 $a[i]$ 插入到树状数组中，这里的树状数组就相当于一个桶，$ans+=i-sum(a[i])$，其中$sum(a[i])$ 为位置 $i$ 前所有小于等于 $i$的数字个数，而$i-sum(a[i])$ 为为位置 $i$ 前所有大于 $i$的数字个数，即满足逆序对的定义，就可以求出正确答案了。
逆向求解
逆向遍历，每次将$ans+=sum(a[i]-1)$，即位置 $i$ 后所有小于 $i$的数字个数，满足逆序对的定义，再将 $a[i]$ 插入树状数组之中。
- 警钟敲烂 在 $add$ 函数中 $i$ 的范围是 $\max(a[1],a[2],a[3],......,a[n])$，并不是 $n$。
离散化
以上方法只对于小数据起作用，一下方法讲解大数据方法。
由于$\max(a[1],a[2],a[3],......,a[n])$过大，数组装不下，离散化只需求出数组 $a$ 每个数的相对大小，例如：
| 1|
| -----------: |
| 原数组 | $147$ | $792$ | $283$ |
| :----------: | :----------: | :----------: | :----------: |
| 离散化数组 | $1$ | $3$ | $2$ |
但是，有时候会遇到数组元素相同的情况，例如：
| 原数组 | $283$ | $792$ | $283$ |
| :----------: | :----------: | :----------: | :----------: |
| 离散化数组 | $1$ | $3$ | $2$ |
逆序对数量与原来不相同。
尝试优化，可以进行如下改变：若 $a[i]=a[j]$，则 $a[i]$ 和 $a[j]$ 在离散化数组中的相对位置也相同，例如：
| 原数组 | $283$ | $792$ | $283$ |
| :----------: | :----------: | :----------: | :----------: |
| 离散化数组 | $1$ | $2$ | $1$ |
求出离散化数组中逆序对的个数，即求出了原数组中逆序对的个数。
二位树状数组之区间修改，区间查询
$sum_{n,m}=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=1}^i\sum\limits_{l=1}^j d_{k,l}$
在矩阵 $[1,1]$ 到 $[n,m]$，推一下 $d_{k,l}$ 出现的次数，不难发现，$d_{k,l}$ 出现的次数为 $(n-k+1)\cdot(m-l+1)$。
例如，$d_{1,1}$ 在每个左上角为 $(1,1)$ 的矩阵都出现过，共出现 $n\cdot m$ 次。
于是将原式展开，有 $sum_{i,j}=\sum\limits_{i=1}^n\sum\limits_{j=1}^m d_{i,j}\cdot(n-i+1)\cdot(m-j+1)$
强拆后，得 $sum_{i,j}=\sum\limits_{i=1}^n\sum\limits_{j=1}^m d_{i,j}(nm-nj+n-mi+ij-i+m-j+1)$
整理，有 $sum_{i,j}=\sum\limits_{i=1}^n\sum\limits_{j=1}^m d_{i,j}((nm+n+m+1)-i(m+1)-j(n+1)+ij)$
于是 $sum_{i,j}=\sum\limits_{i=1}^n\sum\limits_{j=1}^m d_{i,j}(nm+n+m+1)-d_{i,j}i(m+1)-d_{i,j}j(n+1)+d_{i,j}ij$
显然，在这里要维护四个树状数组：$d_{i,j},d_{i,j}i,d_{i,j}j,d_{i,j}ij$。
P4514 上帝造题的七分钟