tag: %u6570%u7EC4.md

Tag: 数组

3 posts
单调栈

栈里只留”还在等下一个更大元素”的候选人。新人 进来,把所有 的栈顶通通弹掉 —— 它们的”下一个更大”就是 。每个元素进栈一次出栈一次, 收工。

...
双指针技巧

一句话: 用两个指针的相对运动,把 暴力压成 之所以能压,是因为问题里藏着单调性 — 移动一个指针让”目标”单调变化,所以根本不需要回头。

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