「数据结构」树状数组

树状数组($Binary\ Indexed\ Trees$)是一个维护__前缀和__的数据结构，需要支持以下操作

• $Add\ x\ y$，单点增加，a[x] += y
• $Query\ x$，查询前缀和

前置知识

$lowbit$运算

$lowbit(n)$表示非负整数$n$在二进制表示下__最低位的1及其后边所有的0构成的数值__

为了实现$lowbit$运算，先把$n$取反，此时第$k$位变为$0$(设第$k$位是$1$，其后均为$0$)，第$0\sim k-1$位变为$1$，再整体加一，所以第$k$位变为$1$，其后为$0$，其前每位恰好与原数相反，再按位求与($&$)即可得到。由于在补码下，$\sim n=-1-n$，所以

$$lowbit(n)=n\ &\ (\sim n+1)=n\ &\ -n$$

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

算法实现

对于一个原序列$a[]$，可以建立一个数组$tree[]$，来保存$a$的区间$[x-lowbit(x)+1, x]$内值的和，即

$$tree[x] = \sum_{i=x-lowbit(x)+1}^x{a[i]}$$

同时$tree$数组可以看成一个树形结构，并满足以下性质

• 每个节点$tree[x]$保存以$x$为根的子树中所有叶节点的和
• 每个节点$tree[x]$的子节点个数等于$lowbit(x)$的位数
• 除树根外，每个节点$tree[x]$的父亲节点为$tree[x+lowbit(x)]$
• 树的深度为$\log_2n$

根据这些性质，就很容易地写出代码

struct BIT {
    int tree[maxn], n, m;
    int lowbit(int k) { return k & -k; }
    void add(int x, int k) {
        for (; x <= maxn; x += x & -x) tree[x] += y;
    }
    int query(int x) {
        int ans = 0;
        for (; x; x -= x & -x) ans += tree[x];
        return ans;
    }
    int init() {
		for (int i = 1; i <= n; ++i) {
			add(i, a[i]);
        }
    }
};

实际上，树状数组可以嵌套维护，来解决更多问题，例如区间修改

$Luogu$模板题目

Luogu P3374 树状数组1 (单点修改，区间查询)

Luogu P3368 树状数组2 (区间修改，单点查询)

Luogu P3372 线段树1 (区间修改，区间查询)