模板——数据结构

发表于 分类于 ， 阅读次数： 作者 Pomelorin

模板——数据结构

ST 表，Trie 树，线段树，树状数组，并查集，动态开点线段树，主席树，lower_bound 用法，树套树，笛卡尔树，树链剖分。

ST 表

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
#include<bits/stdc++.h>
using namespace std;
const int V = 17, N = 200000 + 5;
int st[V + 5][N], b[N], n, m;

int main() {
    int x, y, len;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &st[0][i]);
    for (int i = 1; i <= V; i++)
        for (int j = 1; j <= n; j++)
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); //区间最大max 区间最小min
    /*     f[i-1][j]     f[i-1][j+2^(i-1)]
       |----------------|----------------|
                 total: f[i][j]               */
    for (int i = 1; i <= V; i++) //快速得到 log_2 N
        b[1 << i] = 1;
    for (int i = 1; i <= n; i++)
        b[i] += b[i - 1];
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        len = y - x + 1;
        printf("%d\n", max(st[b[len]][x], st[b[len]][y + 1 - (1 << b[len])]));
    }
    return 0;
}

Trie 树

经常在一些二进制相关题目中使用（01-Trie），出现二进制应考虑。

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
#define mset(a) memset(a,0,sizeof(a))
const int FOUND = 1, VISITED = 2, UNFOUND = 3; //找到了，重复找，未找到
struct Trie {
    int index = 0; //用以做编号
    struct Node {
        int qcnt = 0, exist = 0, etc; //字符串访问次数，是否为字符串等附加信息
        int son[50] = {}; //儿子节点
        //字符串这里意为完整的、自根节点到叶子节点组成的字符串
    } node[500000 + 10];

    int getid(char ch) { return ch - 'a'; }

    void insert(char s[]) //插入操作
    {
        int sons, root = 0, len = strlen(s);
        for (int i = 0; i <= len - 1; i++) {
            sons = getid(s[i]);
            if (!node[root].son[sons])
                node[root].son[sons] = ++index;
            root = node[root].son[sons];
        }
        node[root].exist = 1; //标记这是个字符串
    }

    int find(char s[]) //查询操作
    {
        int sons, root = 0, len = strlen(s);
        for (int i = 0; i <= len - 1; i++) {
            sons = getid(s[i]);
            if (!node[root].son[sons])
                return UNFOUND;
            root = node[root].son[sons];
        }
        if (!node[root].exist)
            return UNFOUND;
        if (!node[root].qcnt) {
            node[root].qcnt++;
            return FOUND;
        }
        return VISITED;
    }
} trie;

线段树

  1. 维护哪些信息？区间和。
  2. 维护哪些标记？区间加标记。
  3. 如何合并区间信息？直接相加。
  4. 如何快速修改区间信息？加上 增量乘区间长度。
  5. 如何合并标记？直接相加。

单点修改，区间查询

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
#define ll long long
#define lson (root*2)
#define rson ((root*2)+1)
#define mid ((l+r)/2)

struct SGT {
    ll t[N * 4];

    void update(ll root,ll l,ll r,ll pos,ll data) {
        if (l == r) {
            t[root] += data;
            return;
        }
        if (pos <= mid)
            update(lson, l,mid, pos, data);
        if (pos > mid)
            update(rson,mid + 1, r, pos, data);
        t[root] = t[lson] + t[rson];
    }

    ll query(ll root,ll l,ll r,ll x,ll y) {
        if (x <= l && y >= r)
            return t[root];
        ll ansl = 0, ansr = 0;
        if (x <= mid)
            ansl = query(lson, l,mid, x, y);
        if (y > mid)
            ansr = query(rson,mid + 1, r, x, y);
        return ansl + ansr;
    }

    void build(ll root,ll l,ll r,ll d[]) {
        if (l == r) {
            t[root] = d[l];
            return;
        }
        build(lson, l,mid, d);
        build(rson,mid + 1, r, d);
        t[root] = t[lson] + t[rson];
        return;
    }
} Tree;

区间修改，区间查询

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
#define ll long long
#define lson (root*2)
#define rson ((root*2)+1)
#define mid ((l+r)/2)

struct SGT {
    struct Node {
        ll data, tag;
    } t[N * 4];

    void pushdown(ll root,ll l,ll r) {
        ll tag = t[root].tag;
        if (t[root].tag == 0)
            return;
        t[lson].data += tag * (mid - l + 1);
        t[rson].data += tag * (r - mid);
        t[lson].tag += tag;
        t[rson].tag += tag;
        t[root].tag = 0;
        return;
    }

    void update(ll root,ll l,ll r,ll x,ll y,ll data) {
        if (x <= l && y >= r) {
            t[root].data += data * (r - l + 1);
            t[root].tag += data;
            return;
        }
        pushdown(root, l, r);
        if (x <= mid)
            update(lson, l,mid, x, y, data);
        if (y > mid)
            update(rson,mid + 1, r, x, y, data);
        t[root].data = t[lson].data + t[rson].data;
    }

    ll query(ll root,ll l,ll r,ll x,ll y) {
        if (x <= l && y >= r)
            return t[root].data;
        pushdown(root, l, r);
        ll ansl = 0, ansr = 0;
        if (x <= mid)
            ansl = query(lson, l,mid, x, y);
        if (y > mid)
            ansr = query(rson,mid + 1, r, x, y);
        return ansl + ansr;
    }

    void build(ll root,ll l,ll r,ll d[]) {
        if (l == r) {
            t[root].data = d[l];
            return;
        }
        build(lson, l,mid, d);
        build(rson,mid + 1, r, d);
        t[root].data = t[lson].data + t[rson].data;
        return;
    }
} Tree;

树状数组

普通

1
2
3
4
5
6
7
8
9
10
11
ll lb(ll x) { return x & (-x); }
void update(ll x, ll data) {
    while (x <= n)
        c[x] += data, x += lb(x);
}
ll query(ll x) {
    ll ans = 0;
    while (x >= 1)
        ans += c[x], x -= lb(x);
    return ans;
}//query(r)-query(l-1)

二维

1
2
3
4
5
6
7
8
9
10
11
12
13
int lb(int x) { return x & -x; }
void update(int x, int y, int data) {
    for (int i = x; i <= n; i += lb(i))
        for (int j = y; j <= m; j += lb(j))
            t[i][j] += data;
}
int query(int x, int y) {
    int ret = 0;
    for (int i = x; i; i -= lb(i))
        for (int j = y; j; j -= lb(j))
            ret += t[i][j];
    return ret;
}

并查集

路径压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct UFDS {
    ll dad[M], n;
    void init(ll p) {
        n = p;
        for (ll i = 1; i <= n; i++)
            dad[i] = i;
    }
    ll find(ll x) {
        while (x != dad[x])
            x = dad[x] = dad[dad[x]];
        return x;
    }
    void merge(ll x, ll y) {
        ll d1 = find(x), d2 = find(y);
        dad[d1] = d2;
    }
    bool check(ll x, ll y) {
        ll d1 = find(x), d2 = find(y);
        if (d1 == d2)
            return 1;
        return 0;
    }
} ufds;

按秩合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void start(int n) {
    for (int i = 1; i <= n; i++)
        dad[i] = i, rank[i] = 0; //树的高度为0
    return;
}
ll find(ll x) {
    while (x != dad[x])
        x = dad[x];
    return x;
}
void merge(int x, int y) {
    int d1 = find(x), d2 = find(y);
    if (d1 == d2) return;
    if (rank[d1] > rank[d2])
        swap(d1, d2);
    dad[d1] = d2;
    if (rank[d1] == rank[d2]) //如果相等，只能增加树高
        rank[d2]++;
    return; //否则树高是不增加的
}

动态开点线段树

普通

通常没有 build 操作。

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
typedef long long ll;
const ll N = 35 * 500000 + 10;
ll cnt = 0;

struct SGT {
    struct node {
        int lson, rson, data;
    } t[N];

#define lson t[root].lson
#define rson t[root].rson
#define mid ((l+r)/2)

    ll update(ll root, ll l, ll r, ll pos, ll data) {
        if (root == 0)
            root = ++cnt; //开辟新节点
        if (l == r) {
            t[root].data += data;
            return root;
        }
        if (pos <= mid)
            lson = update(lson, l, mid, pos, data);
        else
            rson = update(rson, mid + 1, r, pos, data);
        t[root].data = t[lson].data + t[rson].data;
        return root; //返回地址
    }

    ll query(ll root, ll l, ll r, ll x, ll y) {
        ll ret = 0;
        if (root == 0)
            return 0;
        if (x <= l && r <= y)
            return t[root].data;
        if (x <= mid)
            ret += query(lson, l, mid, x, y);
        if (y >= mid + 1)
            ret += query(rson, mid + 1, r, x, y);
        return ret;
    }
} Tree;//root[i] = Tree.update(root[i], 1, n, l, r);

可持久化数组

通常有 build 操作。一次单点修改，最多会让一个线段树上 \(\log ⁡n\) 个节点发生改变，相邻历史版本其余的点可以共用。这样一次更改的时间复杂度是 \(\log ⁡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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N = 1000000 + 10;
ll n, m, a[N], root[N], cnt;

struct SGT {
    struct node {
        int lson, rson, data;
    } t[N * 30];

#define lson t[root].lson
#define rson t[root].rson
#define mid ((l+r)/2)

    int clone(int pos) {
        t[++cnt] = t[pos];
        return cnt;
    }

    int build(int root, int l, int r, int a[]) {
        root = ++cnt;
        if (l == r) {
            t[root].data = a[l];
            return root;
        }
        lson = build(lson, l,mid, a);
        rson = build(rson,mid + 1, r, a);
        return root;
    }

    int update(int root, int l, int r, int pos, int data) {
        root = clone(root); //克隆一个点，现在它们暂时左右儿子公有
        if (l == r) {
            t[root].data = data;
            return root;
        }
        if (pos <= mid)
            lson = update(lson, l,mid, pos, data);
        else
            rson = update(rson,mid + 1, r, pos, data);
        return root;
    }

    int query(int root, int l, int r, int pos) {
        if (l == r)
            return t[root].data;
        if (pos <= mid)
            return query(lson, l,mid, pos);
        else
            return query(rson,mid + 1, r, pos);
    }
} Tree;

int main() {
    int t1, t2, t3, t4;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    root[0] = Tree.build(root[0], 1, n, a);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &t1, &t2, &t3);
        if (t2 == 1) {
            scanf("%d", &t4);
            root[i] = Tree.update(root[t1], 1, n, t3, t4);
        } else {
            printf("%d\n", Tree.query(root[t1], 1, n, t3));
            root[i] = root[t1];
        }
    }
    return 0;
}

主席树

静态区间第 \(k\) 小。对于原序列的每一个前缀 $ [1…i]$ 建立出一棵值域线段树维护各个数出现次数，则其树是可减的。主席树的每个节点保存的是一棵线段树，维护的区间信息，结构相同，具有可加减性（关键），利用可加减性同时行动。充分利用共同数据来减少时间和内存消耗。

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
#include<bits/stdc++.h>
#define mid ((l+r)/2)
using namespace std;

const int N = 1000000 + 10;
int n, m, a[N], rnk[N], root[N], cnt = 0, end;

struct SGT {
    struct node {
        int lson, rson, size;
    } t[N * 30];

    int clone(int pos) //继承上一个历史版本节点，再更新本次历史版本的信息
    {
        t[++cnt] = t[pos];
        t[cnt].size++; //树节点维护元素个数
        return cnt;
    }

    int build(int root, int l, int r) {
        root = ++cnt;
        if (l == r)
            return root;
        t[root].lson = build(t[root].lson, l,mid);
        t[root].rson = build(t[root].rson,mid + 1, r);
        return root;
    }

    int update(int pre, int l, int r, int pos) {
        int root = clone(pre);
        if (l == r)
            return root;
        if (pos <= mid)
            t[root].lson = update(t[root].lson, l,mid, pos);
        else
            t[root].rson = update(t[root].rson,mid + 1, r, pos);
        return root;
    }

    int query(int x, int y, int l, int r, int rnk) {
        //线段树上二分
        if (l == r)
            return l;//返回坐标 l
        int Lsize = t[t[y].lson].size - t[t[x].lson].size;
        if (rnk <= Lsize)
            return query(t[x].lson, t[y].lson, l, mid, rnk);
        else
            return query(t[x].rson, t[y].rson, mid + 1, r, rnk - Lsize);
    }
} Tree;

int main() {
    int t1, t2, t3;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        rnk[i] = a[i];
    }
    sort(rnk + 1, rnk + 1 + n);
    end = unique(rnk + 1, rnk + 1 + n) - (rnk + 1); //离散化
    root[0] = Tree.build(root[0], 1, end); //建初始版本树
    for (int i = 1; i <= n; i++) //建各历史版本树
    {
        int t1 = lower_bound(rnk + 1, rnk + 1 + end, a[i]) - rnk;
        //对于元素单调上升的数列
        //lower_bound：返回第一个大于等于给定数的位置。
        //upper_bound：返回第一个大于给定数的位置。
    	//默认，从小到大排列，找第一个>=
    	// lower_bound( begin , end , val , less<int>());
    	//从大到小，找第一个<=
    	// lower_bound( begin , end , val , greater<int>());
        root[i] = Tree.update(root[i - 1], 1, end, t1);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &t1, &t2, &t3);
        t3 = Tree.query(root[t1 - 1], root[t2], 1, end, t3);
        printf("%d\n", rnk[t3]); //注意输出对象
    }
    return 0;
}

树套树

现在给出 \(1∼n\) 的一个排列，按照某种顺序依次删除 \(m\) 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。外部负责维护集合的增改，内部负责具体的数据。

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
85
86
87
88
#include<bits/stdc++.h>
using namespace std;

//树状数组套动态开点线段树
typedef int ll;
const ll N = 100000 + 10, M = 1000000000;
ll cnt = 0, n, m, pos[N], root[N];
long long ans = 0, del = 0;

struct SGT {
    struct node {
        int lson, rson, data;
    } t[N * 30 * 30];

#define lson t[root].lson
#define rson t[root].rson
#define mid ((l+r)/2)

    ll update(ll root, ll l, ll r, ll pos, ll data) {
        if (root == 0)
            root = ++cnt;
        if (l == r && r == pos) {
            t[root].data += data;
            return root;
        }
        if (pos <= mid)
            lson = update(lson, l,mid, pos, data);
        else
            rson = update(rson,mid + 1, r, pos, data);
        t[root].data = t[lson].data + t[rson].data;
        return root;
    }

    ll query(ll root, ll l, ll r, ll x, ll y) {
        ll ret = 0;
        if (root == 0)
            return 0;
        if (x <= l && r <= y)
            return t[root].data;
        if (x <= mid)
            ret += query(lson, l,mid, x, y);
        if (y >= mid + 1)
            ret += query(rson,mid + 1, r, x, y);
        return ret;
    }
} Tree;

ll lb(ll x) { return x & -x; }

ll query(ll rt, ll x, ll y) {
    ll ret = 0;
    while (rt >= 1) {
        ret += Tree.query(root[rt], 1, n, x, y);
        rt -= lb(rt);
    }
    return ret;
}

void update(ll rt, ll x, ll data) {
    while (rt <= n) {
        root[rt] = Tree.update(root[rt], 1, n, x, data);
        rt += lb(rt);
    }
}

int main() {
    ll tmp, root;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &tmp);
        pos[tmp] = i;
        ans += query(i - 1, tmp + 1, n);
        update(i, tmp, 1);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &tmp);
        printf("%lld\n", ans);
        root = pos[tmp];
        del = 0;
        del += query(root - 1, tmp + 1, n);
        del += query(n, 0, tmp - 1); //由于树状数组维护的是前缀和，
        del -= query(root, 0, tmp - 1); //所以这样搞。
        ans -= del;
        update(root, tmp, -1);
    }
    return 0;
}

笛卡尔树

笛卡尔树是一种特殊的二叉树，每一个节点由一个键值二元组构成，并且同时满足以下两个性质：

  • 键——二叉搜索树（BST）性质：对于树中的每一个节点，其左子树中的所有节点的值都小于该节点的值；其右子树中的所有节点的值都大于该节点的值。这保证了树在中序遍历时会按照输入序列的顺序访问元素。
  • 值——堆性质：如果我们将笛卡尔树看作是一个最大堆或最小堆，则对于每个节点来说，它的值要么不小于或者不大于其子节点的值。具体采用哪种堆取决于应用场景。

经常用于最值维护、最近公共祖先问题。例如柱状图找面积最大的矩形。

1
2
3
4
5
6
7
8
9
10
11
12
13
int cartesian_build(int n) {
    // 建树，满足小根堆性质
    for (int i = 1; i <= n; i++) {
        int k = i - 1;
        while (tree[k].val > tree[i].val)
            k = tree[k].par;
        tree[i].ch[0] = tree[k].ch[1];
        tree[k].ch[1] = i;
        tree[i].par = k;
        tree[tree[i].ch[0]].par = i;
    }
    return tree[0].ch[1];
}

树链剖分

对一棵树分成几条链，把树形变为线性，减少处理难度。链加、链查询，子树加、子树查询。

只有链可以倍增，只有子树可以 dfs 序。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
using namespace std;
// #define int long long
//树链剖分

int p;
const int N = 100005;
int nn, a[N], sum[4 * N], lz[4 * N];
vector<int> m[N];
//父亲 深度 子树大小 重儿子
int father[N], dep[N], siz[N], son[N]; //第一次dfs处理的数据
//重链顶端 dfs序 用来记录dfs序的数
int top[N], dfn[N], num = 1; //第二次dfs处理的数据

void build(int n, int l, int r) {
    if (l == r) {
        sum[n] = a[r];
        return;
    }
    int mid = (l + r) >> 1;
    build(2 * n, l, mid);
    build(2 * n + 1, mid + 1, r);
    sum[n] = sum[2 * n] + sum[2 * n + 1];
    sum[n] %= p;
    return;
}

int search(int n, int l, int r, int x, int y) {
    if (x <= l && y >= r) { return sum[n]; }
    int mid = (l + r) >> 1;
    lz[2 * n] += lz[n];
    lz[2 * n + 1] += lz[n];
    sum[2 * n] += lz[n] * (mid - l + 1);
    sum[2 * n + 1] += lz[n] * (r - mid);
    lz[n] = 0;
    int ans = 0;
    if (x <= mid) {
        ans += search(2 * n, l, mid, x, y);
    }
    if (y > mid) {
        ans += search(2 * n + 1, mid + 1, r, x, y);
    }
    return ans % p;
}

void update(int n, int l, int r, int x, int y, int k) {
    if (x <= l && y >= r) {
        lz[n] += k;
        sum[n] += k * (r - l + 1);
        return;
    }
    int mid = (l + r) >> 1;
    lz[2 * n] += lz[n];
    lz[2 * n + 1] += lz[n];
    sum[2 * n] += lz[n] * (mid - l + 1);
    sum[2 * n + 1] += lz[n] * (r - mid);
    lz[n] = 0;
    if (x <= mid) {
        update(2 * n, l, mid, x, y, k);
    }
    if (y > mid) {
        update(2 * n + 1, mid + 1, r, x, y, k);
    }
    sum[n] = sum[2 * n] + sum[2 * n + 1];
    sum[n] %= p;
    return;
}

void dfs1(int x, int f, int d) {
    father[x] = f;
    dep[x] = d;
    siz[x] = 1;
    for (int c: m[x]) {
        if (c != f) {
            dfs1(c, x, d + 1);
            siz[x] += siz[c];
            if (siz[c] > siz[son[x]]) {
                son[x] = c;
            }
        }
    }
    return;
}

void dfs2(int x, int t) {
    top[x] = t;
    dfn[x] = num++;
    if (son[x] == 0)return;
    dfs2(son[x], t);
    for (int c: m[x]) {
        if (c != son[x] && c != father[x]) {
            dfs2(c, c);
        }
    }
    return;
}

void updRange(int x, int y, int k) {
    while (top[x] != top[y]) {
        //直到两点在同一条链
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        update(1, 1, nn, dfn[top[x]], dfn[x], k);
        x = father[top[x]];
    }
    if (dep[x] > dep[y])swap(x, y);
    update(1, 1, nn, dfn[x], dfn[y], k);
    return;
}

int qRange(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        //直到两点在同一条链
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        ans += search(1, 1, nn, dfn[top[x]], dfn[x]);
        x = father[top[x]];
    }
    if (dep[x] > dep[y])swap(x, y);
    ans += search(1, 1, nn, dfn[x], dfn[y]);
    return ans % p;
}

void updSon(int x, int k) {
    update(1, 1, nn, dfn[x], dfn[x] + siz[x] - 1, k);
}

int qSon(int x) {
    return search(1, 1, nn, dfn[x], dfn[x] + siz[x] - 1) % p;
}

signed main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int n, t, r;
    cin >> n >> t >> r >> p;
    nn = n;
    int aa[n + 1]; //用来临时储存点权，因为dfn序还没排好
    for (int i = 1; i <= n; i++) {
        cin >> aa[i];
    }
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        m[x].push_back(y);
        m[y].push_back(x);
    }
    dfs1(r, 0, 1);//r是根节点
    dfs2(r, r);
    //把aa的数据给到a
    for (int i = 1; i <= n; i++) {
        a[dfn[i]] = aa[i] % p;
    }
    build(1, 1, n);
    //初始化over
    while (t--) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            //从x到y的路劲+k
            int x, y, k;
            cin >> x >> y >> k;
            updRange(x, y, k % p);
        } else if (opt == 2) {
            //查询从x到y的路劲的和
            int x, y;
            cin >> x >> y;
            cout << qRange(x, y) << endl;
        } else if (opt == 3) {
            //x的子树都+k
            int x, k;
            cin >> x >> k;
            updSon(x, k % p);
        } else if (opt == 4) {
            //查询x的子树的和
            int x;
            cin >> x;
            cout << qSon(x) << endl;
        }
    }
    return 0;
}