树状数组¶

BIT，核心作用：单点修改，区间查询 这两个操作都是O(logn)，而且代码极短

1. 为什么要用树状数组？¶

若一个题目，要对数组里的某个元素进行修改，还要求某一个区间的和 1. 若我们用普通数组，那修改是O(1), 求区间和是O(n) 2. 若用前缀和数组，那求区间和是O(1), 修改是O(n) 而树状数组这两个操作都是O(logn)

2. 核心原理：lowbit¶

核心原理在于二进制使用lowbit技巧，取出最右边的1 x&(-x)与上负的自己（其实和计组里面求补码是同个原理）

3. 结构理解¶

树状数组维护一个数组 \(C\)（Tree 数组），其中 \(C[i]\) 不仅保存 \(A[i]\) 的值，而是保存一段区间的和。 * \(C[i]\) 管理的区间长度：就是 lowbit(i)。 * \(C[i]\) 管理的区间范围：\((i - \text{lowbit}(i), i]\)。例如： c[1] (0001) 管理长度 1，区间[1, 1] c[2] (0010) 管理长度 2，区间[1, 2] 也就是下标减去最右侧1再+1

这样求a[1]找c[1]就好了，想要求a[2]，那么求c[2] - c[1]就可以了

注意：树状数组一定要从下标 1 开始！（因为 lowbit(0) = 0 会导致死循环）。

4. 树状数组的能力范围¶

普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。 - 结合律：(𝑥 ∘𝑦) ∘𝑧 =𝑥 ∘(𝑦 ∘𝑧)，其中 ∘ 是一个二元运算符。 - 可差分：具有逆运算的运算，即已知 𝑥 ∘𝑦 和 𝑥可以求出 𝑦。像求区间最大值，最小值这些，就不是树状数组的能力范围

5. 树状数组的树形态¶

奇数下标是最底层的，c[i]只存a[i]自己，lowbit越大，层数越高每个x的父节点是x + lowbit(x)，

6. 两种操作¶

（1）区间查询 (Query)¶

要求a[1] + ... + a[x]，那么本质上是把c数组里不重叠的区间拼起来方法：从x开始，不断减去最右边的1

（2）单点修改（update）¶

给a[i]加上k，那么要给c数组里所有带有i的节点都更新方法：从i开始，不断加上lowbit(i)，直到超过数组上限

7. 模板¶

时刻牢记树状数组下标从 1 开始。

# 下标 1-based, tree 全局或局部均可
def add(i, x):
    while i <= n:
        tree[i] += x
        i += i & -i

def query(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

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

建树：建一个0列表，对每个位置都进行一次单点增加

import sys  

data = map(int, sys.stdin.read().split())  
iterator = iter(data)  
n, m = next(iterator), next(iterator)  
a = []  
for i in range(n):  
    a.append(next(iterator))  

def add(i, x):  
    while i <= n:  
        c[i] += x  
        i += i & (-i)  

def query(i):  
    res = 0  
    while i > 0:  
        res += c[i]  
        i -= i & (-i)  
    return res  

# 建树  
c = [0] * (n + 1)  # 下标从1开始  
for i in range(n):  
    add(i + 1, a[i])  

ans = []  
for _ in range(m):  
    opt, x, ky = next(iterator), next(iterator), next(iterator)  
    if opt == 1:  
        add(x, ky)  
    else:  
        ans.append(str(query(ky) - query(x - 1)))  # 是x - 1不是x  

print('\n'.join(ans))