跳转至

猫树

O(1)查询，O(n\log n)建树，不支持修改的线段树
要求区间有可合并的性质

在没有修改的情况下优化结构或数据内容，使查询更简单。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
#define LL long long

const int maxn=200005;
const int logn=21;
const int inf=0x3f3f3f3f;

struct Data {
    int sum,Max;
} data[logn][maxn];

#define lid id<<1
#define rid id<<1|1

int a[maxn],lg[maxn<<2],dep[maxn<<2];

void build(int id,int l,int r,int d=1){
    if(l==r) return;

    dep[id]=d; // 存下来在第几层
    int mid=l+r>>1;
    build(lid,l,mid,d+1),build(rid,mid+1,r,d+1);

    Data *p=data[d];
    // 向左边跑 线性求最大前缀序列、最大子序列
    int sum=a[mid], Max=a[mid];
    p[mid]={a[mid],a[mid]};
    for(int i=mid-1;i>=l;i--){
        sum+=a[i],Max=max(Max,0)+a[i];
        p[i].sum = max(sum,p[i+1].sum);
        p[i].Max = max(Max,p[i+1].Max);
    }
    // 向右边跑
    sum=a[mid+1], Max=a[mid+1];
    p[mid+1]={a[mid+1],a[mid+1]};
    for(int i=mid+2;i<=r;i++){
        sum+=a[i],Max=max(Max,0)+a[i];
        p[i].sum = max(sum,p[i-1].sum);
        p[i].Max = max(Max,p[i-1].Max);
        // 有可能保持不变，有可能重新开始算
    }
}

int hbit,n,m,mod;
void init(){
    memset(data,-0x3f,sizeof(data));

    while((1<<hbit) < n) hbit++;
    n=1<<hbit;
    // 叶子数量和最左侧叶子编号是一样的

    for(int i=2;i<=4*n;i++)
        lg[i]=lg[i>>1]+1;
}

LL qry(int l,int r) {
    if(l==r) return a[l]; // 建树没有到叶子...
    int x=(1<<hbit)+l-1,y=(1<<hbit)+r-1; // 叶子在树上的编号 画图吧
    int layer = dep[x>>(lg[x^y]+1)];   // 快速定位到层数 x==y 会寄
    return std::max({data[layer][l].Max,data[layer][r].Max,data[layer][l].sum+data[layer][r].sum});
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n; mod=n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    init();
    build(1,1,n);
    int m,l,r;
    cin >> m >> l >> r;

    LL lastans=0,ans=0;
    for(int i=1;i<=m;i++){
        lastans = qry(min(l,r),max(l,r));
        ans^=abs(lastans*i);
        l=(2*l+lastans)%mod+1,r=(2*r+lastans)%mod+1;
    }
    cout << ans << '\n';
}

引理

在查询\([l,r]\)这段区间的信息和的时候，将线段树树上代表\([l,l]\)的节点和代表\([r,r]\)这段区间的节点在线段树上的\(LCA\)求出来，设这个节点\(p\)代表的区间为\([L,R]\)，我们会发现一些非常有趣的性质：

  1. \([L,R]\)这个区间一定包含\([l,r]\)。
  2. \([l,r]\)这个区间一定跨越\([L,R]\)的中点。

过程

普通线段树递归维护一段区间，节点表示一条线段。重点在合并与标记下传。

猫树只需要一次合并。在补点后，相同长度的线段都在同一层。按层划分来维护线段，并在每一层的各个线段上，从mid开始，向左右进行线性dp记录。

记根节点为第0层，编号为1，区间长度为n。叶子节点的层数为 t=lg2(n)+1、最左叶子结点的编号 1<<t。注意到叶子数量和第一个叶子的编号应该相等。

根据引理，找\([l,r]\)时，先求出叶子编号 \(\begin{align} x=2^t-1+l \\ y=2^t-1+r \end{align}\)，通过 lca=x>>(lg2(x^y)+1) 快速定位到lca编号（LCP），若分治则直接打tag，若询问则先用dep数组求出其层数，并合并\([l,mid],[mid+1,r]\)求值。

以求区间最大子段和为例：

在建树递归到非叶子节点时，从mid开始向左跑dp，从mid+1开始向右跑dp。

查询时 \(O(1)\) 到 \(l,r\) 的线段树上LCA那一层查，合并处理\([l,mid],[mid+1,r]\)求出答案。