树状数组 概念 树状数组（Fenwick Tree）是一种数组实现的树状结构，常用于解决前缀和问题。它能够在O(log n)的时间内进行单点更新与区间查询操作，特别适用于在动态变化的数组中进行频繁的前缀和查询和更新。 通常需要对输入数据进行离散化，因为数据通常是不连续，而数组要求索引连续 操作 单点修改：更改数组中一个元素的值 区间查询：查询一个区间内所有元素的和 范围：[1, n]; 例如：7（111） 单点修改：111 -> 1000 区间查询：111 -> 110 -> 100 前缀和模板 注意不能add(0, val)，无法跳出循环，因为lowbit(0) = 0 1234567891011121314151617181920212223242526class FenwickTree { int[] tr; // [1, n] public FenwickTree(int[] nums) { // [0, n-1] this.tr = new int[nums.length+1]; f ...