D001单修区查，单查区修，区查区修模板，如何为？
摘要：树状数组（Binary Indexed Tree, BIT，也称 Fenwick Tree）是算法竞赛中极其常用的数据结构。它的核心优势在于：代码短小精悍、常数极小、内存占用少。 虽然它的功能是线段树的子集，但在处理“动态前缀和”相关问题时
树状数组（Binary Indexed Tree, BIT，也称 Fenwick Tree）是算法竞赛中极其常用的数据结构。它的核心优势在于：代码短小精悍、常数极小、内存占用少。
虽然它的功能是线段树的子集，但在处理“动态前缀和”相关问题时，BIT 通常是首选。
来自董晓算法，对两个关键函数原理的图解
BIT 结构模板为
class BIT:
def __init__(self, n):
self.tree = [0] * (n + 1) # 初始化为一颗空树
def add(self, i, val):
while i < len(self.tree):
self.tree[i] += val
i += i & -i
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def query(self, l, r): # 查询区间为 [l, r]
return self.sum(r) - self.sum(l - 1)
已知大小为 \(n\) 的数组，有两种初始化方式一种为 \(O(n\log n)\) 一种为 \(O(n)\) 。