为什么要用树状数组？

        一般地，对于一个给定区间  进行区间更新和查询，都需要线性遍历该区间，时间复杂度为O(n) ，当查询次数较多时，可能会超时。而树状数组是一类通过树型结构存储，将区间处理复杂度降为 lgn的数据结构。

树状数组的定义

        树状数组的思想是，将一些小节点的信息同时储存在对应的大节点中，大节点的信息同时存储在更大的节点中，以此类推。这样，我们对某个区间进行更新或查询时，就不需要遍历所有的基础节点，而只需要遍历保存了这些基础节点信息的大节点即可。这些存储区间信息的树型结构就被称为树状数组。

图片示例（自己画的不是很好看，哈哈）

最下面的八个黄色方块就代表数组m，记录着要处理数组的原始数据。而上方参差不齐的白色方块，则代表着记录数组 m信息的树状数组n。图中的箭头代表信息存储的位置，如图可以看出，n1管理的就是m1，n2管理的是m1、m2，而n8管理的则是全部m1-m8个数。

lowbit 函数

那么，我们怎么知道 n管理的是 m中的哪个区间，又怎么知道m的信息都存放在哪些n节点中呢？我们引入一个函数：lowbit 来完成这件事情。

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

在常见的计算机中，有符号数采用补码表示。在补码表示下，数 x的相反数-x的补码表示为 x补+1。所以，lowbit 函数可以保留x二进制表示中最低位的1及其后面的全部0。 例如，6的二进制表示为110，其 lowbit值为10。 15的二进制表示为1111，其 lowbit值即为1。而对于2的幂次如8 = 1000，其lowbit值即为自己。

lowbit 值有什么作用呢？我们以6为例，借助上图来看：6加上其 lowbit值2后结果为8。8节点刚好是存储了节点 6信息的，且比 6更大一级的节点；同样地， 6减去其 lowbit 值2后结果为4。 4节点存储的是 m1-m4的信息，刚好是与 6节点存储区间（ 节点存储的是 m5-m6的信息）没有交集的节点。这两个规律，对于所有的值都通用。

所以，有了 lowbit 函数，我们便可以开始了解树状数组的一些基本操作。为了方便，我们下面的代码针对求和一项属性来介绍:

单点更新与区间查询

在树状数组中， mi的信息首先一定是存储在ni中的，在这之后，我们每次将c节点的下标 i 加上lowbit(i)便可以得到更上一级的，也应存储当前信息的 m节点。所以，树状数组中单点更新的代码模板如下：

void update(int pos, int k) { // m[pos] += k
    // n 为树状数组长度
    while(pos <= N) {
        n[pos] += k;
        // 找更上一级的 c 节点下标
        pos += lowbit(pos);
    }
}

当我们要查询数组  的某前缀信息时，例如求  的值，便从  开始查询，若  刚好记录的是  的和，那么直接返回即可；否则，要每次将  节点的下标  减去 ，以找到更前面的信息存储的  节点。所以，树状数组中区间查询的代码模板如下：

long long askis(int pos) { // 求 sum(a[1] - a[pos])
     if(!pos) return 0;
     ll ret = 0;
     while(pos) {
         ret += n[pos];
         // 找更靠前的 c 节点下标
         pos -= lowbit(pos);
     }
     return ret;
}

根据以上两个基本操作，我们还可以拓展一些操作：

long long asksi(int l, int r) { // 查询 a 数组 [l, r] 区间和
    return askis(r) - askis(l - 1);
}
 
long long askss(int pos) { // 查询 a[pos] 单点的值
    return askis(pos) - askis(pos - 1);
}

区间更新与区间查询:

那么，我们如何进行区间更新呢？

根据前缀和与差分数组的知识，如果我们想对某个区间进行更新，我们只需对其差分数组的区间两端进行更新，并在查询时进行前缀求和即可。而在之前的介绍中，我们发现，树状数组可以以  的复杂度查询某个数组  的前缀和。所以，我们可以用树状数组来解决区间更新和查询的问题。

假设我们要对数组  进行区间更新及查询，那么我们维护序列  的差分数组 。也即，有 。区间更新时，便只需要对差分数组  进行单点更新；区间查询时，假设我们对  的一个前缀  求和，结果即为：

所以，原数组  的区间查询问题，便可以通过维护两个树状数组，分别记录  和  的值即可。

在代码中，第一个树状数组  就是 sum，第二个树状数组  则用 ntimessum 表示，对应的区间更新代码如下：

void update(int pos, int k) {
     int x = pos;
     while(pos <= n) {
         sum[pos] += k;
         ntimessum[pos] += k * (x - 1);
         pos += lowbit(pos);
     }
 }
 
void update_internal(int l, int r, int k) { // a[l]-a[r] 加上指定值 k
    // 类似于前缀和 + 差分
    update(l, k);
    update(r + 1, -k);
}

而当我们要对区间  进行区间查询时，代码如下

long long askii(int pos) {
     if(!pos) return 0;
     ll ret = 0, x = pos;
     while(pos) {
         ret += x * sum[pos] - ntimessum[pos];
         pos -= lowbit(pos);
     }
     return ret;
 }
 
long long asklr(int l, int r) { // 查询 [l, r] 区间和
    return askii(r) - askii(l - 1);
}

综上所述，我们介绍了如何利用树状数组进行区间处理问题。下面，我们给出整体模板。

class BIT {
    using ll = long long;
    const int N = 1e5 + 5;
 
public:
    int n;
    vector<ll> sum;
    vector<ll> ntimessum;
 
    BIT(): n(N), sum(N + 5, 0), ntimessum(N + 5, 0) {}
    BIT(int _n): n(_n + 5), sum(_n + 10, 0), ntimessum(_n + 10, 0) {}
    ll lowbit(ll x) {
        return x & (-x);
    }
 
    void update(int pos, ll k) { // 单点更新
        ll x = pos;
        while(pos <= n) {
            sum[pos] += k;
            ntimessum[pos] += k * (x - 1);
            pos += lowbit(pos);
        }
    }
 
    void update_internal(int l, int r, int k) { // 区间更新
        update(l, k);
        update(r + 1, -k);
    }
 
    ll askis(int pos) { // 区间更新后的单点查询、单点更新后的范围查询
     if(!pos) return 0;
        ll ret = 0;
        while(pos) {
            ret += sum[pos];
            pos -= lowbit(pos);
        }
        return ret;
    }
 
    ll asksi(int l, int r) { // 单点更新后的区间查询
        if(l > r) {
            //cout << "Interval invalid!\n";
            return 0;
        }
        return askis(r) - askis(l - 1);
    }
 
    ll askss(int pos) { // 单点更新后的单点查询
        return askis(pos) - askis(pos - 1);
    }
 
    ll askii(int pos) { // 区间更新后的前缀查询
     if(!pos) return 0;
        ll ret = 0, x = pos;
        while(pos) {
            ret += x * sum[pos] - ntimessum[pos];
            pos -= lowbit(pos);
        }
        return ret;
    }
 
    ll asklr(int l, int r) { // 区间更新后的区间查询
        return askii(r) - askii(l - 1);
    }
};

以下是针对模板的一些说明：

首先，与一般数组不同，我们的树状数组下标是从  开始的。所以，如果需要进行下标访问，需要将题目中的下标 。

其次，如果需要进行单点更新 + 区间查询操作，应使用 update 函数以及 asksi 函数；如果需要进行区间更新 + 区间查询操作，则需要使用 update_internal 及 asklr 函数。

最后，本模板只针对求和功能。针对一些其他类型题目，比如较为经典的最长上升子序列问题，也可以修改本模板来使用。