UOJ Logo immortalCO的博客

博客

一种高效处理无修改区间或树上询问的数据结构（附代码）

2016-11-02 19:45:47 By immortalCO

问题描述

给出一个某种元素的序列 $a_1,a_2,...,a_n$，要求进行 $m$ 次询问，每一次是询问一段区间 $[l,r]$ 的某种支持结合律和快速合并的信息，要求在线。

这类问题比较通用，比如在 DP 的优化中就常常见到。

要求复杂度尽量优秀，假设合并复杂度为 $O(1)$。

以下的时间复杂度 $O(A) + O(B) + O(C)$ 表示预处理复杂度、单次询问的复杂度和空间复杂度。

各种性质的具体问题

可减信息，如区间和、区间异或和

直接用前缀和实现，复杂度 $O(n)+O(1)+O(n)$。

可重复贡献信息，如区间最值

如果序列很长，使用线段树即可，复杂度 $O(n)+O(\log n)+O(n)$。

如果询问很多，但序列不是特别长，可以用倍增的 RMQ，复杂度 $O(n\log n)+O(1) + O(n\log n)$。

如果序列很长，询问也很多，可以对序列线性建立笛卡尔树转为 LCA 问题，然后转为正负 1 RMQ，每 $\log n$ 分一段打表预处理，复杂度 $O(n)+O(1)+O(n)$。

仅满足支持结合律和快速合并，如最大子段和、区间的串哈希值

一般使用线段树实现，复杂度 $O(n) + O(\log n) + O(n)$。

一种新的做法

上面一般做法的问题是：询问复杂度不够优秀。

如果问题没有任何性质，一般只能使用线段树。然而在实际的问题（或所优化的问题）中，由于询问不受空间大小的限制，一般询问的次数是大大多于序列的长度的，比如有的莫队需要查询 $O(n\sqrt n)$ 次的区间最值，这样倍增 RMQ 就有了用武之地。因此，我们考虑能否像 RMQ 那样，在一般的问题上，以预处理的时间和空间，换取快速的询问。

考虑一个询问 $[l,r]$。如果 $l=r$，则我们可以直接得出答案。否则，考虑 $[l,r]$ 在线段树上定位时，是在哪个线段树节点 $p$ 中同时递归到左右两个儿子（如果 $[l,r]$ 只定位为线段树上的一个节点，则视为同时递归进入两个儿子）。设该节点的区间 $[s, t)$，其中点为 $m$（两个一半的区间是 $[s,m)$ 和 $[m,t)$），那么区间一定是满足 $s\le l < m \le r < t$。如果我们对于每个 $l\le i < m$ 都预处理了 $[i,m)$ 的信息和 $prel(p,i)$，对于每个 $m \le i < r$ 都预处理了 $[m,i]$ 的信息和 $prer(p,i)$，那么所求的信息和就是 $prel(p,l)+prer(p,r)$。这一步是 $O(1)$ 的。现在唯一的问题是我们能否快速求出 $p$。

一般的线段树没有什么好的性质，但如果一棵线段树的值域是 $[0, 2^k-1)$，并且编号遵从堆式存储（$i$ 的儿子为 $2i$ 和 $2i+1$），那么 $[l,r]$ 所定位的区间，就是 $[l,r]$ 所对应的两个节点的 LCA，也就是 $l,r$ 两个位置对应节点的编号的二进制数的 LCP！获得 $x,y$ 的二进制数的 LCP 只需要使用 x >> Log2[x ^ y]（找出并丢弃第一个不同的二进制位及后面的位），其中 Log2 数组可以线性预处理，因此求出 $p$ 也只需要 $O(1)$ 的时间。这样，我们就得到了一种 $O(n\log n)+O(1)+O(n\log n)$ 的优秀算法。

我们称这一数据结构为猫树。

应用

经典问题：区间最大子段和

给出一个序列，多次询问区间的最大子段和。

这是一个经典的模型。不同于经典做法，我们只需要记录 $prel$、$prer$ 为对应前（后）缀的最大子段和、最大前（后）缀和即可。

复杂度：$O(n\log n)+O(1)+O(n\log n)$。实测在 $n=m=200000,a_i\le 10^9$ 的情况下，此做法的运行时间接近经典做法（非递归线段树实现）的 $2\over 3$。

经典问题：NAND

给出一个序列，多次询问一个 $x$ 对一个区间中所有数按顺序依次 NAND 的结果。

NAND 没有结合律，因此我们要用一些经典的处理方式。NAND 是按位独立的，因此我们可以对每一位维护信息：如果这一位刚开始是 0，那么按顺序 NAND 了这个区间中的所有数后会变成什么；如果这一位是 1 那么会变成多少。用位运算可以优化为 $O(1)$ 的信息合并。

使用猫树，即可直接支持 $O(n\log n)+O(1)+O(n\log n)$。

经典问题：区间凸包

现在来看看不那么傻逼的题。

给出一个平面上的点的序列，每次询问一个区间的凸包的面积，保证横坐标单调递增，强制在线。

这题的凸包不是贡献独立的，因此我们必须求出这个凸包。经典做法是用线段树套可持久化平衡树维护凸包，在线段树的节点直接保存凸包，用可持久化线段树的合并保证复杂度，代码非常繁琐，复杂度为 $O(n \log^2n)+O(\log^2n)+O(n\log^2n)$。

结合猫树，只要我们可持久化地保存 $prel,prer$ 为区间的凸包，这样我们就只需要资磁对左右两边预处理的凸包二分出一个公切线，然后进行计算即可，并不需要直接合并两个平衡树维护的凸包。而这里的凸包由于只有 $x$ 单调的插入，用简单的可持久化数组（线段树或平衡树）即可直接维护，代码量很小。复杂度为 $O(n\log^2n)+O(\log n)+O(n\log^2n)$。

BZOJ4540

给出一个区间，每次询问一个区间 $[l,r]$ 的所有子区间的区间最小值之和。

根据猫树的思想，我们考虑分开来计算代价。其中，$[l,m)$ 和 $[m,r]$ 的答案可以用单调栈线性预处理，就只需要考虑跨越部分了。对 $[l,m)$ 中记录每个数到 $m$ 的区间最小值，考虑这个最小值贡献答案的区间的右端点 $r$，这个最右的右端点可以通过左右的归并得出。这样预处理之后，就能做到 $O(1)$ 的询问复杂度。这里的细节比较繁琐，不过多说明。

这个做法实际运行时间十分优秀，在 $n=100000,m=2\times 10^7$ 的数据可以 $0.3s$ 出解。

扩展？

优化 DP

如果某种 DP 需要按顺序决定，但有很多次的区间查询，我们可以用猫树结合二进制分组做到相同的复杂度。

在查询次数很多的情况下，此做法比直接线段树维护具有优势。

树上无修改询问

考虑把猫树扩展到树上，以资磁快速的链上信息询问。我们对树进行点分治，预处理所有点到重心的信息（需要保存“包括中心”和“不包括重心”两种信息，如果有方向要求要专门考虑），这样同样能拆成两个已经预处理的信息的和。

询问的时候，我们需要找出这条链上最上面的重心。对点分治建立点分树（把重心连成树），然后我们要找到的重心就是询问的链端点的 LCA，这可以用倍增 RMQ 来预处理。

复杂度和区间问题相同，$O(n\log n)+O(1)+O(n\log n)$。

其实 BZOJ4568 是这种做法的离线版本。

UPD：代码参考

区间最大子段和
    const int MaxN = 200010;
    const ll inf = 1000000000000000000ll;
    int val[MaxN], pos[MaxN];
    struct Node
    {
        struct Data {ll pre, sum;} *dl, *dr;
        int mov_l, mov_r;
        IL ll query(RG int l, RG int r)
        {
            return dl[l -= mov_l].sum > dr[r -= mov_r].sum 
                ? dmax(dl[l].sum, dl[l].pre + dr[r].pre)
                : dmax(dr[r].sum, dl[l].pre + dr[r].pre);
        }
    } T[524288];
    int N;
    void build(RG int i, RG int l, RG int r)
    {
        if(l + 1 == r || N <= l) return;
        RG int m = (l + r) >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m, r);

        RG Node *o = T + i;
        o->dl = new Node::Data[m - l], o->mov_l = l;
        o->dr = new Node::Data[r - m], o->mov_r = m;
        RG ll pre, max_pre, sum, max_sum;
        pre = sum = 0, max_pre = max_sum = -inf;
        for(RG int k = m - 1; k >= l; --k)
        {
            pre += val[k],                     cmax(max_pre, pre);
            sum = dmax(sum, 0) + val[k],    cmax(max_sum, sum);
            o->dl[k - l] = (Node::Data) {max_pre, max_sum};
        }
        pre = sum = 0, max_pre = max_sum = -inf;
        for(RG int k = m; k <= r - 1; ++k)
        {
            pre += val[k],                     cmax(max_pre, pre);
            sum = dmax(sum, 0) + val[k],    cmax(max_sum, sum);
            o->dr[k - m] = (Node::Data) {max_pre, max_sum};
        }
    }
    int pre[1024];

    IL void main()
    {
        RG int (*F)() = read<int>;
        RG int n = N = F();
        Rep(i, 0, n) val[i] = F();
        RG int D = 1; while(D < n) D <<= 1;
        build(1, 0, D);
        RG int l, r, d, v;
        pre[0] = 0;
        Rep(i, 1, 1024) pre[i] = pre[i >> 1] + 1;
        Rep(_, 0, F())
        {
            l = F() - 1, r = F() - 1;
            if(l == r) Print(val[l]);
            else
            {
                l += D, r += D;
                v = l ^ r;
                d = (v < 1024 ? pre[v] : 10 + pre[v >> 10]);
                Print(T[l >> d].query(l - D, r - D));
            }
        }
        io::flush();
    }
BZOJ4540
    const int MaxN = 131072;
    int a[MaxN], N;
    // 对单调栈中的数进行归并，并确定每一位对应的单调栈中元素
    struct Node
    {
        int m;
        struct Data
        {
            int pos;            // 在左右单调栈中的排名
            ll sum, ans;        // 答案的和
            ll pre;                // 到中点这一段的和
        } *pre;
        IL ll query(RG int l, RG int r)
        {
            RG int pl = pre[l].pos, pr = pre[r].pos;
            return pre[l].pre + pre[r].pre + ((pl < pr)
                ? pre[l].ans + (m - l)       * (pre[r].sum - (pl == m - l        ? 0 : pre[l + pl - 1].sum))
                : pre[r].ans + (r - m + 1) * (pre[l].sum - (pr == r - m + 1 ? 0 : pre[r - pr + 1].sum)));
        }
    } T[262144];
    void build(RG const int i, RG const int l, RG const int r)
    {
        if(l + 1 == r || N <= l) return;
        RG const int m = T[i].m = (l + r) >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m, r);

        RG Node::Data *f = T[i].pre = (new Node::Data[r - l]) - l;

        static int stack[MaxN], b[MaxN];
        RG int top, cur, V; RG ll pre, ran, sum;
        pre = sum = top = ran = 0; cur = 2000000000; *stack = m;
        for(RG int i = m - 1; i >= l; --i)
        {
            V = a[i];
            for(; top && a[stack[top]] >= V; --top)
                ran -= (ll) a[stack[top]] * (stack[top - 1] - stack[top]);
            ran += (ll) V * (stack[top] - i);
            stack[++top] = i;
            cmin(cur, V); 
            f[i].sum = (sum += (b[i] = cur));
            f[i].pre = (pre += ran);
        }
        pre = sum = top = ran = 0; cur = 2000000000; *stack = m - 1;
        for(RG int i = m; i <= r - 1; ++i)
        {
            V = a[i];
            for(; top && a[stack[top]] >= V; --top)
                ran -= (ll) a[stack[top]] * (stack[top] - stack[top - 1]);
            ran += (ll) V * (i - stack[top]);
            stack[++top] = i;
            cmin(cur, V);
            f[i].sum = (sum += b[i] = cur);
            f[i].pre = (pre += ran);
        }
        sum = 0;
        RG int pl = m - 1, pr = m, N = 0, tmp;
        while(l <= pl || pr < r)
            (pr >= r || (l <= pl && b[pl] > b[pr]))
                ? (f[pl].pos = ++N, (tmp = (N - (m - pl)))         ? sum += (ll) b[pl] * tmp : 0, f[pl--].ans = sum)
                : (f[pr].pos = ++N, (tmp = (N - (pr - m + 1)))     ? sum += (ll) b[pr] * tmp : 0, f[pr++].ans = sum);
    }

    IL void main()
    {
        RG int (*F)() = read<int>;
        RG int n = N = F(), m = F(), D = 1;
        while(D < n) D <<= 1;
        Rep(i, 0, n) a[i] = F();
        build(1, 0, D);
        RG int l, r, v, d;
        static int pre[1024];
        Rep(i, 1, 1024) pre[i] = pre[i >> 1] + 1;
        while(m--)
        {
            l = F() - 1, r = F() - 1;
            if(l == r) Print(a[l]);
            else
            {
                l += D, r += D;
                v = l ^ r;
                d = (v < 1024 ? pre[v] : 10 + pre[v >> 10]);
                Print(T[l >> d].query(l - D, r - D));
            }
        }
        io::flush();
    }
代码的模板
//pb_ds 20160711
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <cmath>
#include <iostream>
using namespace std;
#define RG register
#define IL __inline__ __attribute__((always_inline))
#define For(i, a, b) for(RG int i = a, ___u = b; i <= ___u; ++i)
#define Dor(i, a, b) for(RG int i = b, ___d = a; i >= ___d; --i)
#define Rep(i, a, b) for(RG int i = a, ___u = b; i != ___u; ++i)
#define dmin(a, b) ((a) < (b) ? (a) : (b))
#define dmax(a, b) ((a) > (b) ? (a) : (b))
#define cmin(a, b) ((a) > (b) ? (a) = (b) : 1)
#define cmax(a, b) ((a) < (b) ? (a) = (b) : 1)
#define ddel(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))
#define dabs(i) ((i) > 0 ? (i) : -(i))
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef long double ld;

#include <queue>
#include <vector>

namespace pb_ds
{   
    // 输入输出优化模板从此开始
    namespace io
    {
        const int MaxBuff = 1 << 15;
        const int Output = 1 << 23;
        char B[MaxBuff], *S = B, *T = B;
        //#define getc() getchar()
        #define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
        char Out[Output], *iter = Out;
        IL void flush()
        {
            fwrite(Out, 1, iter - Out, stdout);
            iter = Out;
        }
    }

    template<class Type> IL Type read()
    {
        using namespace io;
        RG char ch; RG Type ans = 0; RG bool neg = 0;
        while(ch = getc(), (ch < '0' || ch > '9') && ch != '-')     ;
        ch == '-' ? neg = 1 : ans = ch - '0';
        while(ch = getc(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
        return neg ? -ans : ans;
    }
    template<class Type> IL void Print(RG Type x, RG char ch = '\n')
    {
        using namespace io;
        if(!x) *iter++ = '0';
        else
        {
            if(x < 0) *iter++ = '-', x = -x;
            static int s[100]; RG int t = 0;
            while(x) s[++t] = x % 10, x /= 10;
            while(t) *iter++ = '0' + s[t--];
        }
        *iter++ = ch;
    }
    // 输入输出优化模板到此结束

    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
}

int main()
{
    #define FILE "dev"
    //freopen(FILE ".in", "r", stdin), freopen(FILE ".out", "w", stdout);
    pb_ds::main();
    fclose(stdin), fclose(stdout);  
}

完结撒花

评论

dick32165401
orz immortalCO
matthew99
你是不是可以每一层按根号分块。。。对每一块再继续按根号分块（也就是第二层是根号的根号）。。。然后询问我们还是可以利用r和l的差找到对应的层，这样复杂度O(nloglogn)+O(1)+O(nloglogn)?
Sengxian
Mark 一下，NOIP 完了以后来研究......
Claris
这个感觉就是把分治的过程记录下来？ 如果允许离线的话，利用Tarjan算法，维护加权并查集也可以实现这个功能。
SkyDec
本质上就是离线分治？
WuHongxun
这个做法就是把分治过程记录下来吧，这个LCA直接RMQ就是询问O(1)了啊
neither
为什么要叫猫树啊-_-
Cat_shao
如果我时间复杂度没算错的话，可以用分块 + 猫树进一步优化时间复杂度/空间复杂度。以区间询问为例（上树也可，这里就不赘述了），将整个序列分为若干个块长为 $\log n$ 的块，每个块内开一棵猫树，每个块维护前缀“和”、后缀“和”，再以块为单位架一棵猫树。对于左右端点不在同一个块的询问，由 散块（预处理好的后缀和） + 整块（以块为单位的猫树） + 散块（预处理好的前缀和）得到。对于左右端点在同一个块的询问，直接由这个块内的猫树得到。
wangzhifang
对于区间最大子段和的问题，我们可以使用四毛子在此基础上进一步优化成线性时空预处理，常数时空查询：块间的询问很容易解决，显然关键在块内询问的处理，我们如果一直继续递归套娃的话复杂度感觉确实只能到 $\log^*$（迭代对数），我们重新考虑类似 RMQ 的压位方式，对于一个长度为 $l$ 的块，我们很好说明其子区间的答案区间只和 $\frac{l(l+1)}{2}$ 个子区间的区间和是否大于等于 $0$ 这 $2^{l(l+1)/2}$ 的信息量有关，因此我们可以在 $\Theta(l^2 2^{l(l+1)/2})$ 的时空复杂度内预处理出所有块的所有子区间作为询问区间时的答案区间，查询时只要查表然后用预处理好的前缀和就能 $\Theta(1)$ 算出答案。

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-11-21 14:31:11