共 2 篇相关文章
树状数组（Binary Indexed Tree）是一种用于高效处理动态序列单点更新与区间求和问题的数据结构。其核心思想是利用二进制表示和 lowbit 操作，构建一个辅助数组，将前缀和查询与单点更新的时间复杂度均优化至 O(log N)。文章从暴力解法的瓶颈出发，逐步剖析 lowbit 函数的原理与实现、树状数组的结构定义、求和与更新操作的具体步骤，并说明了如何通过前缀和数组将初始化复杂度降至 O(N)。进一步，文章阐述了每个树状数组元素所管辖的区间范围及其在更新与查询过程中的变化规律。此外，还介绍了树状数组与差分数组结合以处理区间更新问题、二维树状数组的扩展，以及利用树状数组求解逆序对数量的应用场景与离散化处理技巧。
前缀和是一种高效的数组预处理技术，用于解决区间和查询问题。其核心思想是预先计算数列前n项的累计和，生成一个前缀和数组，使得任意区间的和可以通过简单的减法运算快速获得。这种方法将每次查询的时间复杂度从O(n)降低到O(1)，代价是需要额外的O(n)空间存储前缀和。在具体应用中，例如LeetCode 303题“区域和检索 - 数组不可变”，要求对给定数组频繁执行区间求和操作。通过初始化时构建前缀和数组（其中prefix[0]为0，prefix[i]表示原数组前i-1项的和），sumRange(left, right)方法可以直接返回prefix[right+1] - prefix[left]，避免了重复遍历数组的开销。该模式特别适合数据不可变且查询密集的场景，是优化动态规划或滑动窗口等问题的常见辅助手段。掌握前缀和有助于提升算法效率，尤其在处理大数据集或实时查询时，能显著减少计算成本。
