tag: %u6570%u7EC4.md

Tag: 数组

1 posts
树状数组
树状数组,也称为二进制索引树,是一种支持单点更新和区间查询的数据结构。在大多数情况下,我们可以用它来查询区间和、区间乘积或其他满足以下条件的操作: 结合律: 具有逆运算,我们可以通过 和 推断出 它基于这样一个假设:任何前缀 都可以分解为最多 个区间,这些区间的信息是已知的。 从上图可以看出,每个位置 控制的区间的右边界是 。在树状数组中, 被分配控制长度为 的区间。这里, ...