今天重温了一下树状数组，资料链接：https://oi-wiki.org/ds/fenwick/#_2

树状数组和线段树非常类似，不过树状数组的代码量比线段树小太多了，而且不容易出bug，所以学习树状数组还是非常有必要的。

树状数组主要理解这几个要点：①lowbit含义及原理②差分的思想

一、lowbit含义

lowbit返回值为$x\&(-x)$，我们知道树状数组除了叶子结点其余结点都是记录一个区间的信息的，在线段树中我们通过传递结点控制的左右子树来递归处理区间的信息，而树状数组结点掌握的区间信息则需要通过lowbit来进行计算。

lowbit主要计算结点x的二进制从右往左数第一个1及其右边所有0组成的十进制数，举个栗子，$(88)_{10}=(1011000)_2$，则$lowbit(88)=(1000)_2=(8)_{10}$

所以结点88能控制8个原序列的信息，为什么$x\&(-x)$就能计算出控制的个数呢？因为按照二进制，负数的二进制是正数的二进制取反后+1，所以$(-88)_{10}=(0100111)_2+(1)_2=(0101000)_2$，正好进行逻辑与运算后只剩最后四位，也就lowbit所要计算的数。

二、差分的思想

树状数组在进行区间加（区间修改）操作的时候，因为树状数组并没有像线段树一样使用标记数组来对修改的信息进行标记，所以这里使用差分的思想可以将区间修改转化为点修改

令$b_i=a_i-a_{i-1}$，我们可以发现，区间加的时候，例如$[l,r]$区间内所有数都加$x$，差分的优势在于$[l+1,r]$区间内$b_i$的值是不变的，所以我们不用修改$[l+1,r]$的b值，只用修改l和r+1处的b值即可，原$b_{r+1}=a_{r+1}-a_r$，现$b_{r+1}=a_{r+1}-(a_r+x)=a_{r+1}-a_r-x$，所以我们要对r+1处的b值加上-x，同理l处b值应该加上x。

接下来将区间求和转化为差分后数组的求和公式，$\sum\limits_{i=1}^ra_i=\sum\limits_{i=1}^r\sum\limits_{j=1}^ib_j=\sum\limits_{i=1}^rb_1+b_2+\cdots+b_i=rb_1+(r-1)b_2+\cdots+b_r=\sum\limits_{i=1}^rb_i*(r-i+1)$

则$\sum\limits_{i=l}^ra_i=\sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i=\sum\limits_{i=1}^{l-1}b_i*(r-l+1)+\sum\limits_{i=l}^rb_i*(r-i+1)$

第一项用树状数组维护$b_i$，第二项用树状数组维护$i*b_i$

例题1：

题目链接：https://loj.ac/problem/132

刚才的讲解其实就是题解QAQ

代码：

例题2：（树状数组+离散化求逆序对）

题目链接：https://www.luogu.com.cn/problem/P1908

题解：先离散化，将序列的值调整在1~n范围内，然后将离散后的值倒着插入树状数组，每次插入查询比当前数小的值有多少个，将这些数求和即是答案

代码：

树状数组O(n)建树+求第k大（待UPD）