没进水的脑子


——博客——

数据结构小结

  • ~14.16K 字
  1. 1. 数据结构小结
    1. 1.1. 线段树
      1. 1.1.1. 1.什么是线段树?
      2. 1.1.2. 2.基本操作
      3. 1.1.3. 3.代码:
    2. 1.2. 树状数组
      1. 1.2.1. 1.什么是树状数组?
      2. 1.2.2. 2.如何维护?
      3. 1.2.3. 3.什么是lowbit?
      4. 1.2.4. 4.基本操作
      5. 1.2.5. 5.代码:
    3. 1.3. 平衡树
      1. 1.3.1. 1.什么是平衡树?
      2. 1.3.2. 2.实现方法
      3. 1.3.3. 3.代码:
    4. 1.4. 分块
      1. 1.4.1. 1.什么是分块?
      2. 1.4.2. 2.基本操作
      3. 1.4.3. 3.代码:
      4. 1.4.4. 4.练习推荐
    5. 1.5. 完结挖坑

数据结构小结

  • 该文章主要用于存放数据结构思想和板子，具体做题思想以后补

  • 挖坑:线段树专题、分块专题、平衡树专题

线段树

1.什么是线段树?

线段树本质就是一个二叉树，树上每个节点维护一段区间的值。

2.基本操作

  • 建树(build)

    • 就是从1号节点开始，每次劈两半，作为做儿子和右儿子，当发现当前结点的左右边界相等时，该节点的值即为建树序列的值。

  • 查询(query)

    • 递归查找，左边大于查找的左区间就查左儿子，右边同理。

  • 修改(update)

    • 如果修改区间覆盖当前区间，则直接给当前区间加上懒标记，否则递归查找加懒标记。

  • 传递懒标记(push_down)

    • 下传就完了。

3.代码:

Code
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
class Segment_tree {
		struct node {
			int val, tag;
			node(int val = 0, int tag = 0) : val(val), tag(tag) {}
		};
		node *tree;
#define ls(x) x<<1
#define rs(x) x<<1|1
#define mid ((l+r)>>1)
	public:
		Segment_tree(int siz) {
			tree = new node[siz]();
		}
		void push_up(int p) {
			tree[p].val = tree[ls(p)].val + tree[rs(p)].val;
		}
		void build(int l, int r, int p, int *a) {
			if (l == r) {
				tree[p].val = a[l];
				return;
			}
			build(l, mid, ls(p), a);
			build(mid + 1, r, rs(p), a);
			push_up(p);
		}
		void add_tag(int l, int r, int p, int val) {
			tree[p].tag += val;
			tree[p].val += (r - l + 1) * val;
		}
		void push_down(int l, int r, int p) {
			if (tree[p].tag) {
				add_tag(l, mid, ls(p), tree[p].tag);
				add_tag(mid + 1, r, rs(p), tree[p].tag);
				tree[p].tag = 0;
			}
		}
		void update(int l, int r, int p, int ql, int qr, int val) {
			if (l >= ql && r <= qr) {
				add_tag(l, r, p, val);
				return;
			}
			push_down(l, r, p);
			if (ql <= mid)update(l, mid, ls(p), ql, qr, val);
			if (qr > mid)update(mid + 1, r, rs(p), ql, qr, val);
			push_up(p);
		}
		int query(int l, int r, int p, int ql, int qr) {
			int ans = 0;
			if (l >= ql && r <= qr) return tree[p].val;
			push_down(l, r, p);
			if (ql <= mid) ans += query(l, mid, ls(p), ql, qr);
			if (qr > mid) ans += query(mid + 1, r, rs(p), ql, qr);
			return ans;
		}
};
Segment_tree tree(N * 4);
int a[N];
signed main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	tree.build(1, n, 1, a);
	while (m--) {
		int opt, x, y;
		cin >> opt >> x >> y;
		if (opt == 1) {
			int k;
			cin >> k;
			tree.update(1, n, 1, x, y, k);
		} else cout << tree.query(1, n, 1, x, y) << endl;
	}
}

树状数组

1.什么是树状数组?

树状数组主要是利用二进制的性质来维护的数据结构，虽然不如线段树全能，但是比线段树简短，只不过思想可能难以理解。

2.如何维护?

每一个节点维护与其直连接点的和，具体可以看下面的图。

3.什么是lowbit?

lowbit就是找到一个数二进制下最后一个1。

代码:

lowbit(x)=x&(-x)

4.基本操作

  • 单点修改(update)

    从所选节点开始，增加自身及其父节点的值。

  • 区间查询(query)

    记录每个节点的前缀和，查询时用右范围的前缀和减去左范围。

5.代码:

Code
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
#include <bits/stdc++.h>
using namespace std;
//因为树状数组没有明确的树形结构，所以就不写类了。
const int N = 2e6 + 10;
int n, m;
int tree[N];
#define lowbit(x) ((-x)&x)
void add(int x, int val) {
	while (x <= n) tree[x] += val, x += lowbit(x);
}
int query(int x) {
	int ans = 0;
	while (x != 0) {
		ans += tree[x];
		x -= lowbit(x);
	}
	return ans;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int aa;
		cin >> aa;
		add(i, aa);
	}
	while (m--) {
		int opt, a, b;
		cin >> opt >> a >> b;
		if (opt == 1) add(a, b);
		else cout << query(b) - query(a - 1) << endl;
	}
}

平衡树

1.什么是平衡树?

平衡树的出现是由于在某些情况下，二叉树的复杂度会因为重心的偏移而退化成 ，为了防止这种情况的出现，我们强行将二叉树变为平衡树，来确保遍历的时间复杂度。

2.实现方法

因为平衡树的实现方法实在是太多了，没有办法(懒得)给大家展示，因此这里只给出Splay和FHQ的代码。

3.代码:

Splay
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
183
184
185
186
template <class T>
class Splay
{
        struct Node
        {
                T v;
                int cnt, size;
                Node *fa, *son[2];
                bool dir;
                Node()
                {
                        fa = son[0] = son[1] = nullptr;
                        cnt = size = 0;
                }
                bool get_dir()
                {
                        return fa ? this == fa->son[1] : 0;
                }
                void update()
                {
                        size = cnt;
                        if (son[0])
                                size += son[0]->size;
                        if (son[1])
                                size += son[1]->size;
                        return;
                }
        };
        Node *tree, *root = nullptr, *now = nullptr;

public:
        Splay(int siz = 1e5 + 10)
        {
                tree = new Node[siz]();
                now = tree;
        }
        int get_size(Node *x)
        {
                return (x ? x->size : 0);
        }
        void link(Node *fa, Node *son, int p)
        {
                if (fa)
                        fa->son[p] = son;
                if (son)
                        son->fa = fa;
                return;
        }
        void rotate(Node *x)
        {
                Node *f = x->fa, *ff = f->fa;
                int ck = x->get_dir(), ckf = f->get_dir();
                link(f, x->son[ck ^ 1], ck);
                link(x, f, ck ^ 1);
                link(ff, x, ckf);
                f->update();
                x->update();
                return;
        }
        void splay(Node *x, Node *goal)
        {
                if (!x)
                        return;
                while (x->fa != goal)
                {
                        if (x->fa->fa != goal)
                                rotate(x->get_dir() == x->fa->get_dir() ? x->fa : x);
                        rotate(x);
                }
                if (!goal)
                        root = x;
                return;
        }
        void insert(T x)
        {
                Node *r = root, *fa = nullptr;
                while (r && x != r->v)
                        fa = r, r = r->son[x > r->v];
                if (r)
                        r->cnt++;
                else
                {
                        r = now++;
                        r->v = x, r->size = r->cnt = 1;
                        r->son[0] = r->son[1] = nullptr;
                        r->fa = fa;
                        if (fa)
                                fa->son[x > fa->v] = r;
                }
                splay(r, nullptr);
                return;
        }
        void find(int x)
        {
                Node *r = root;
                if (!r)
                        return;
                while (x != r->v && r->son[x > r->v])
                        r = r->son[x > r->v];
                splay(r, nullptr);
                return;
        }
        Node *get_lower(int x)
        {
                find(x);
                Node *r = root;
                if (!r)
                        return nullptr;
                if (r->v < x)
                        return r;
                r = r->son[0];
                while (r && r->son[1])
                        r = r->son[1];
                return r;
        }
        Node *get_upper(int x)
        {
                find(x);
                Node *r = root;
                if (!r)
                        return nullptr;
                if (r->v > x)
                        return r;
                r = r->son[1];
                while (r && r->son[0])
                        r = r->son[0];
                return r;
        }
        int get_rank(int x)
        {
                Node *u = get_lower(x);
                if (u)
                        splay(u, nullptr);
                return (u ? u->size - get_size(u->son[1]) : 0) + 1;
        }
        int get_kth(int x)
        {
                Node *r = root;
                if (r->size < x)
                        return 0x3f3f3f3f;
                while (1)
                {
                        Node *l = r->son[0];
                        if (get_size(l) + r->cnt < x)
                                x -= get_size(l) + r->cnt, r = r->son[1];
                        else if (x <= get_size(l))
                                r = l;
                        else
                        {
                                splay(r, nullptr);
                                return r->v;
                        }
                }
        }
        void erase(int x)
        {
                Node *l = get_lower(x), *r = get_upper(x);
                splay(l, nullptr);
                splay(r, l);
                Node *&del = ((r || l) ? (r ? r->son[0] : l->son[1]) : root);
                if(del->cnt>1)
                        del->cnt--,splay(del,nullptr);
                else del=nullptr;
                return;
        }
};
#include <iostream>
using namespace std;
int n;
const int N=1e5+100;
Splay<int>tree(N);
int main()
{
        scanf("%d,",&n);
        while(n--)
        {
                int a,b;
                scanf("%d%d",&a,&b);
                if(a==1) tree.insert(b);
                else if(a==2) tree.erase(b);
                else if(a==3) printf("%d\n",tree.get_rank(b));
                else if(a==4) printf("%d\n", tree.get_kth(b));
                else if(a==5) printf("%d\n", tree.get_lower(b)->v);
                else if(a==6) printf("%d\n", tree.get_upper(b)->v);
        }
}
FHQ
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
#include <stdlib.h>
template<class T> 
class FHQ {
		struct Node {
			int cnt, size, rnd;
			T v;
			Node* son[2];
			void update() {
				size = cnt;
				if (son[0]) size += son[0]->size;
				if (son[1]) size += son[1]->size;
			}
			Node() {
				son[1] = son[0] = nullptr;
				cnt = size = 0;
				rnd = rand();
			}
		};
		Node *root = nullptr, *tree, *now = nullptr;
	public:
		Node *L, *R;
		FHQ(long long siz = 1e5 + 10) {
			tree = new Node[siz]();
			now = tree;
		}
		long long get_size(Node *x) {
			return x ? x->size : 0;
		}
		long long get_rank(Node *root, T k) {
			Node *l, *r;
			split(root, l, r, k - 1);
			long long ans = get_size(l) + 1;
			root = merge(l, r);
			return ans;
		}
		Node *&get_kth(Node *&x, T k) {
			long long siz = get_size(x->son[0]);
			if (siz + 1 <= k && siz + x->cnt >= k)return x;
			if (siz + 1 > k)return get_kth(x->son[0], k);
			return get_kth(x->son[1], k - x->cnt - siz);
		}
		void split(Node *x, Node *&l, Node *&r, T k) {
			if (!x)return l = r = nullptr, void();
			if (x->v <= k) {
				split(x->son[1], x->son[1], r, k);
				l = x;
			} else {
				split(x->son[0], l, x->son[0], k);
				r = x;
			}
			x->update();
		}
		auto get_lowwer(int x) {
			Node*l, *r;
			split(root, l, r, x - 1);
			auto ans = get_kth(l, l->size)->v;
			root = merge(l, r);
			return ans;
		}
		auto get_upper(int x) {
			Node*l, *r;
			split(root, l, r, x);
			auto ans = get_kth(r, 1)->v;
			root = merge(l, r);
			return ans;
		}
		Node *&merge(Node *&l, Node *&r) {
			if (l == nullptr)return r;
			else if (r == nullptr)return l;
			if (l->rnd < r->rnd) {
				l->son[1] = merge(l->son[1], r);
				l->update();
				return l;
			} else {
				r->son[0] = merge(l, r->son[0]);
				r->update();
				return r;
			}
		}
		void add_node(T k) {
			Node *l, *r, *x;
			split(root, l, r, k);
			if (l && (x = get_kth(l, l->size))->v == k) {
				split(l, l, x, k - 1);
				x->size++, x->cnt++;
			} else {
				x = now++;
				x->cnt = x->size = 1;
				x->v = k;
			}
			root = merge(merge(l, x), r);
		}
		void del_node(T k) {
			Node *l, *r, *mid;
			split(root, l, r, k - 1);
			split(r, mid, r, k);
			if (mid && mid->cnt > 1) mid->cnt--, mid->size--, r = merge(mid, r);
			root = merge(l, r);
		}
		Node *&get_root() {
			return root;
		}
};
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
FHQ<long long>tree(N);
int main() {
	srand(19260817);
	cin >> n;
	tree.add_node(19260817);
	while (n--) {
		int op, x;
		cin >> op >> x;
		if (op == 1) tree.add_node(x);
		if (op == 2) tree.del_node(x);
		if (op == 3) printf("%d\n", tree.get_rank(tree.get_root(), x));
		if (op == 4) printf("%d\n", tree.get_kth(tree.get_root(), x)->v);
		if (op == 5) {
			cout << tree.get_lowwer(x) << endl;
		}
		if (op == 6) {
			cout << tree.get_upper(x) << endl;
		}
	}
}

分块

1.什么是分块?

分块就是将一个大序列分成好几个小块，如果修改范围覆盖一个块就给块打上标记，否则暴力修改。大部分情况下将快长设为 ，当然为了应对有些玄学题的玄学复杂度也可以将块长设为 或者 。

2.基本操作

  • 初始化

    处理出块长，然后 将各个点放在块内(说白了维护个数组，标记某个下表所在的块)。

  • 区间修改、赋值(update)

    和思想一样，遇到大块打标记，遇到零碎点暴力修改，复杂度 。

  • 单点查询(ask)

    看所在的块中有没有标记，有则下传，没有则直接输出。

3.代码:

Code
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 10;
int n;
int b[N];
int st[N];
int ed[N];
int siz[N];
int a[N];
int tag[N];
int len;
int loc[N];
void change(int l, int r, int c) {
	if (loc[l] == loc[r]) {
		for (int i = l; i <= r; i++) a[i] += c;
	} else {
		for(int i=loc[l]+1;i<=loc[r]-1;i++) tag[i]+=c;
		for(int i=l;i<=ed[loc[l]];i++) a[i]+=c;
		for(int i=st[loc[r]];i<=r;i++) a[i]+=c;
	}
}
signed main() {
	cin >> n;
	len = sqrt(n);
	for (int i = 1; i <= len; i++) {
		st[i] = n / len * (i - 1) + 1;
		ed[i] = n / len * i;
		ed[len] = n;
		siz[i] = ed[i] - st[i] + 1;
		for (int j = st[i]; j <= ed[i]; j++) loc[j] = i;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	while (n--) {
		int opt, l, r, c;
		cin >> opt >> l >> r >> c;
		if (!opt) change(l,r,c);
		else cout<<a[r]+tag[loc[r]]<<endl;
	}
}

4.练习推荐

在 loj 上有 9道分块的专题训练 虽然数据很水，但是全部拿分块做下来之后会极大提高对分块的熟练度，十分推荐去做。

完结挖坑

[ ] 线段树题目讲解

[ ] 分块9题讲解

[ ] 平衡树题目讲解