本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-12 12:21:14

void add (int x, int k) { while (x <= n && k > f[x]) f[x] = k, x += lowbit (x); }

int qry (int x, int y)
{
    int res = -1e9;
    while (y >= x) {
        if (y - lowbit (y) > x) res = max (res, f[y]), y -= lowbit (y);
        else res = max (res, z[y]), y--;
    }
    return res;
}

即树状数组求区间最值。

点加的复杂度是显然的。考虑区间查。

$y$ 有两种变化：

• 减去 $\text{lowbit} (y)$
• 减去一

不难发现 $y$ 的减量是不小于一的。然后发现对于情况二，$y$ 的低 $\text{highbit(x)}$ 位一定全都是 $0$，那么这种情况出现次数是 $\log$ 级别的。情况二后紧跟的一定是操作一（因为 $\text{lowbit}(y) \gets 1$），这之后是连续 $\log$ 次的操作一。所以粗略复杂度是 $O(\log^2 n)$。

感性上这个上界有点松了。但我不太会势能分析。