树状数组的扩展应用与多维情景分析

# 1. 树状数组基础知识

树状数组（Binary Indexed Tree，BIT），又称树状树组，在计算机科学中是一种特殊的数据结构，用于高效地处理动态的累计频率查询。树状数组允许动态维护任何前缀的和，并支持在 $O(\log n)$ 的时间内计算任意区间的和。

#### 1.1 树状数组的原理和基本操作

树状数组的核心思想是利用二进制表示中低位1的个数特性来加快求和操作。下面是树状数组的基本操作：
- **初始化**：树状数组的大小一般为原始数组大小加1，全部置为0。
- **更新操作**：从叶子节点开始，每次更新节点的同时更新对应父节点，直到根节点。
- **求和操作**：从叶子节点开始向前计算累积和。

#### 1.2 树状数组在单维情景中的应用实例

假设有一个长度为n的数组a，我们需要支持两种操作：
1. 将数组中某个位置i的值增加delta（a[i] += delta）。
2. 查询数组在区间 [1, k] 的累积和（求和 a[1] + a[2] + ... + a[k]）。

下面是使用树状数组实现上述需求的示例代码：

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
    def upd