Fenwick 树（树状数组）

Fenwick 树（Binary Indexed Tree，二叉索引树）是一种能高效支持更新元素和计算数字表前缀和的数据结构。这使它特别适合表格更新频繁、且需要快速响应各类查询（如求元素之和）的场景。Fenwick 树的更新和查询操作通常都只需 O(log n) 时间，比普通数组和线段树更高效。这种高效性来自它在数组中存储部分和信息，从而可以高效计算区间和——添加元素和求区间和两种操作都能在 O(log n) 时间内完成。