[Note] 树状数组

[L4] 树状数组

1. 生态位

• 识别:

  1. 题目涉及“动态单点/区间修改”与“动态前缀/区间查询”。

  2. 信息满足结合律且可差分（如和、异或、乘积）。

  3. 不能维护( Max/Min )。

• 地位: 基础数据结构。相比线段树更轻量，常用于作为更复杂算法（如 CDQ 分治、扫描线）的底层贡献统计工具。

• 用途: 可以通过 $O(\log N)$ 的复杂度解决动态修改前缀和问题，解决静态前缀和应对多次动态修改的复杂度爆炸问题。

事实上，树状数组能解决的问题是线段树能解决的问题的子集：
树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。
然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。

2. 逻辑支点

核心原理: 二进制拆分降维，

• 将静态的数组转为树状管理。$Bit[x]$ 维护的区间是 $(x - \text{lowbit}(x), x]$。

• 可以参考下图：

下标 $i$	1	2	3	4	5	6	7	8
二进制	0001	0010	0011	0100	0101	0110	0111	1000
$lowbit(i)$	0001	0010	0001	0100	0100	0010	0001	1000

• 具体推导:

  • Lowbit 定义: lowbit(x) = x & -x。利用补码特性，提取出最低位的 $1$。

  • 查询 $Query(x)$: 若要查询 $[1,x]$ 的区间和，向左累积 $x \leftarrow x - lowbit(x)$，每次都跳过了已处理的区间。参考上图理解 $7 \to 6 \to 4 \to 0$。

  • 更新 $update(x,val)$: 若要修改 $x$，向右修改 $x \leftarrow x + \text{lowbit}(x)$，每次都修改第一个能包括当前区间的区间。

2.2 区间修改

• 理论上树状数组也支持区间修改+区间查询，不过此时我们就需要通过差分数组 $D[i]$ 来转换。

$$\sum_{i=1}^{n}(A[i]) = \sum_{i=1}^{n}(\sum_{j=1}^{i}D[j]))$$

• 接着把柿子再展开：

$$\sum_{i=1}^{n}(\sum_{j=1}^{i}D[j])) = \sum_{j=1}^{n}((n-j+1) D[j]) = (n+1)\sum_{j=1}^{n}(D[j]) - \sum_{j=1}^{n}(j \cdot D[j])$$

• 结论：我们可以通过维护两个树状数组来完成这个任务。维护 $D[i]$ 的树状数组 $C_1$。维护 $i \cdot D[i]$ 的树状数组 $C_2$。

2.3 逻辑模型

1. 偏序关系模型：

   • 核心：权值树状数组模型，将数值映射为索引。
   • 转换：扫描序列时，利用 query( x ) 获取已处理元素中满足偏序条件的数量。

2. 动态贡献模型：

   • 核心：配合扫描线，解决区间内“特定属性单体”的贡献问题。
   • 转换：通过"撤销旧位置贡献"，“激活新位置贡献”的策略，确保任何查询区间内，每个单体只产生一次贡献。

3. 特征数值化模型：

   • 核心：将非数值关系（如 $count(A) > count(B)$ ）转化为数值前缀和。
   • 特征：令 $A = 1, B = -1$，$\iff$ 寻找满足 $P[j] - P[i-1] > 0$ 的偏序对。

3. 实战部署

▶

树状数组：单点修改模板

Bit[maxn];

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

void add( int idx, int val )
{
    for( int i = idx; i <= n; i += lowbit( i ) ) 
	{
		Bit[i] += val;
	}
}

int query( int idx )
{
    int res = 0;
    for( int i = idx; i > 0; i -= lowbit( i ) ) 
    {
        res += Bit[i];
    }
    return res;
}

▶

树状数组：区间修改+查询

int Bit1[maxn], Bit2[maxn];

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

// 单点修改
void update( int idx, int val )
{
    for ( int i = idx; i <= n; i += lowbit( i ) )
    {
        Bit1[i] += v;
        Bit2[i] += idx * v;
    }
}

// 区间查询 [1, idx]
int get_sum( int idx )
{
    int res = 0;
    for ( int i = idx; i > 0; i -= lowbit( i ) )
    {
        res += ( idx + 1 ) * Bit1[i] - Bit2[i];
    }
    return res;
}

// 区间修改 [l, r] 增加 v
void range_add( int l, int r, int v )
{
    update( l, v );
    update( r + 1, -v );
}

▶

进阶策略: 处理负数索引

// 场景：数值化后的前缀和存在负数
int offset = 500000;
// 预置基础状态的贡献
add( 0 + offset, 1 ); 

for ( int i = 1; i <= n; ++ i )
{
    int cur_sum = prefix_sum[i];
    // 统计满足特征关系的数量
    ans += query( cur_sum + offset - 1 );
    add( cur_sum + offset, 1 );
}

4. 知识关联

• 母题: P1908 逆序对 BIT —— 经典的权值树状数组应用。

• 实战案例:

  • [[P1972 HH的项链]]: 动态贡献。将区间去重转化为动态点贡献。

  • P5463 小鱼比可爱: 加权贡献。BIT 维护下标和，解决带权子区间统计。

  • [[200_Publish/260_Records/Archive/ABC439F Beautiful Kadomatsu]]: 特征预处理。BIT 仅作为 $O(N \log N)$ 预处理工具，核心在于线性 DP 降维。

  • ABC441E A B substring: 特征数值化。通过 1/-1 转化，将字符串统计降维为偏序关系问题。

• 关联笔记:

  • 降维技巧 树状数组的本质是动态化的差分。

  • 线段树基础理论 当需要维护 Max/Min 或 非差分信息时使用。