树状数组 vs 线段树

树状数组（Fenwick Tree）和线段树（Segment Tree）是两种常用的数据结构，用于解决区间查询问题。下面是两种数据结构的解决方法和代码示例。

1. 树状数组（Fenwick Tree）： 树状数组是一种用于高效实现区间查询的数据结构。它可以在O(log n)的时间复杂度内进行单点更新和区间查询操作。

代码示例：

# 树状数组类
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def query(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

# 使用树状数组解决区间查询问题
def solve_with_fenwick_tree(nums, queries):
    n = len(nums)
    fenwick_tree = FenwickTree(n)
    for i, num in enumerate(nums):
        fenwick_tree.update(i + 1, num)

    res = []
    for query in queries:
        if query[0] == 'update':
            i, delta = query[1], query[2]
            fenwick_tree.update(i + 1, delta)
        elif query[0] == 'query':
            l, r = query[1], query[2]
            res.append(fenwick_tree.query(r + 1) - fenwick_tree.query(l))

    return res

2. 线段树（Segment Tree）： 线段树是一种用于高效实现区间查询的数据结构。它可以在O(log n)的时间复杂度内进行单点更新和区间查询操作。

代码示例：

# 线段树类
class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        self.build(nums, 0, 0, self.n - 1)

    def build(self, nums, i, l, r):
        if l == r:
            self.tree[i] = nums[l]
        else:
            mid = (l + r) // 2
            self.build(nums, 2 * i + 1, l, mid)
            self.build(nums, 2 * i + 2, mid + 1, r)
            self.tree[i] = self.tree[2 * i + 1] + self.tree[2 * i + 2]

    def update(self, i, val):
        self._update(0, 0, self.n - 1, i, val)

    def _update(self, i, l, r, idx, val):
        if l == r:
            self.tree[i] = val
        else:
            mid = (l + r) // 2
            if idx <= mid:
                self._update(2 * i + 1, l, mid, idx, val)
            else:
                self._update(2 * i + 2, mid + 1, r, idx, val)
            self.tree[i] = self.tree[2 * i + 1] + self.tree[2 * i + 2]

    def query(self, ql, qr):
        return self._query(0, 0, self.n - 1, ql, qr)

    def _query(self, i, l, r, ql, qr):
        if l > qr or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.tree[i]
        mid = (l + r) // 2
        left_sum = self._query(2 * i + 1, l, mid, ql, qr)
        right_sum = self._query(2 * i + 2, mid + 1, r, ql, qr)
        return left_sum + right_sum

# 使用线段树解决区间查询问题
def solve_with_segment_tree(nums, queries):
    segment_tree = SegmentTree(nums)
    res = []
    for query in queries:
        if query[0] == 'update':
            i, val = query[1], query[2]
            segment_tree.update(i, val)