一个复杂度的简单分析

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

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