树状数组

概述

树状数组又称 Fenwick 树、二叉索引树，用 O(logn) 维护前缀信息并支持单点修改。借 lowbit 运算取出一个数最低位的 1，每个节点维护一段以自身下标结尾、长为 lowbit 的区间聚合值；修改时下标沿加 lowbit 不断上跳，查询前缀时沿减 lowbit 不断下跳，单次都是对数级。它实现简洁、常数远小于线段树，适合维护前缀和、区间和这类可差分的信息，配合差分数组还能支持区间修改与区间查询。给出 add 与 sum 两个方法的结构体实现，并附单点、区间修改查询等模板例题。

参考资料

• 树状数组 - OI Wiki

简介

树状数组（Binary Indexed Tree，BIT），又称 Fenwick 树，用 $O(\log n)$ 维护前缀信息并支持单点修改。借助 lowbit(x)=x&-x，节点 $c_x$ 维护区间 $(x-\operatorname{lowbit}(x),x]$ 的聚合值。修改时沿 $x\to x+\operatorname{lowbit}(x)$ 上跳，查询前缀时沿 $x\to x-\operatorname{lowbit}(x)$ 下跳，单次操作 $O(\log n)$。它实现简洁、常数小，适合维护前缀和、区间和等可差分的信息。

实现

146 Bcpp

struct BIT
{
	int c[N];
	void add(int u,int v){while(u<N){c[u]+=v;u+=u&-u;}}
	int sum(int u){int res=0;while(u){res+=c[u];u-=u&-u;}return res;}
};

例题

洛谷 P3374 【模板】树状数组 1

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 $x$；
• 求出某区间每一个数的和。

洛谷 P3368 【模板】树状数组 2

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 $x$；
2. 求出某一个数的值。

洛谷 P3372 【模板】线段树 1

如题，已知一个数列 $\{a_i\}$，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

洛谷 P4514 上帝造题的七分钟

维护一个二维矩阵，需要支持以下两种操作：

• 将矩形区域内的所有数字增加 $v$。
• 计算矩形区域内所有数字的总和。