线段树以及其基本操作（V1.1）
2023-08-19 17:02:18
发布于：浙江
31阅读
0回复
0点赞
定义一个类：
class SegmentTree {
public:
int size;
vector<int> tree;
SegmentTree(int n) {
size = n;
tree.resize(4 * n);
}
//后面的函数都写在这里面
};
根据数组递归创建线段树：
void build(vector<int>& arr, int v, int tl, int tr) {
if (tl == tr)
tree[v] = arr[tl];
else {
int tm = (tl + tr) / 2;
build(arr, 2 * v, tl, tm);
build(arr, 2 * v + 1, tm + 1, tr);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
使用以下方式构建一个线段树：
SegmentTree <线段树名称>(<数组长度>);
<线段树名称>.build(<数组名>, <节点>(填1), <左边界>(填0), <右边界>(填<数组长度> - 1) );
例如：
SegmentTree st(n);
st.build(arr, 1, 0, n - 1);
查询区间和 :
int query_sum(int v, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && r == tr)
return tree[v];
int tm = (tl + tr) / 2;
return query_sum(2 * v, tl, tm, l, min(r, tm)) + query_sum(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}
使用以下方式查询区间和：
<线段树名称>.query_sum(1, 0, <数组长度> - 1, <左边界>, <右边界>);
例如：
st.query_sum(1, 0, n - 1, 0, 5)
注意：
查询最小值 [1]:
int query_min(int v, int tl, int tr, int l, int r) {
if (l > r)
return INT_MAX;
if (l == tl && r == tr)
return tree[v];
int tm = (tl + tr) / 2;
return min(query_min(2 * v, tl, tm, l, min(r, tm)), query_min(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
使用以下方式查询最小值：
<线段树名称>.query_min(1, 0, <数组长度> - 1, <左边界>, <右边界>);
例如：
st.query_min(1, 0, n - 1, 0, 5)
注意：
查询最大值 [2]:
int query_max(int v, int tl, int tr, int l, int r) {
if (l > r)
return INT_MIN;
if (l == tl && r == tr)
return tree[v];
int tm = (tl + tr) / 2;
return max(query_max(2 * v, tl, tm, l, min(r, tm)), query_max(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
使用以下方式查询最大值：
<线段树名称>.query_max(1, 0, <数组长度> - 1, <左边界>, <右边界>);
例如：
st.query_max(1, 0, n - 1, 0, 5)
注意：
线段树的创建实例：
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++)
cin >> arr[i];
SegmentTree st(n);
st.build(arr, 1, 0, n - 1);
先输入元素个数n，然后输入n个元素。
例如：
5
1 2 5 4 3
线段树的查询实例：
int q, l, r;
cin >> q;
while (q--) {
cin >> l >> r;
printf("区间和：%d 区间最小值：%d 区间最大值：%d\n", st.query_sum(1, 0, n - 1, l, r), st.query_min(1, 0, n - 1, l, r), st.query_max(1, 0, n - 1, l, r));
}
先输入查询次数q，后面q行每次输入两个数l和r。
例如：
5
0 3
1 2
0 4
3 3
2 4
注意：
线段树实例：
#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
public:
int size;
vector<int> tree;
SegmentTree(int n) {
size = n;
tree.resize(4 * n);
}
//根据列表创建线段树
void build(vector<int>& arr, int v, int tl, int tr) {
if (tl == tr)
tree[v] = arr[tl];
else {
int tm = (tl + tr) / 2;
build(arr, 2 * v, tl, tm);
build(arr, 2 * v + 1, tm + 1, tr);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
//查询区间和
int query_sum(int v, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && r == tr)
return tree[v];
int tm = (tl + tr) / 2;
return query_sum(2 * v, tl, tm, l, min(r, tm)) + query_sum(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}
//查询最小值
int query_min(int v, int tl, int tr, int l, int r) {
if (l > r)
return INT_MAX;
if (l == tl && r == tr)
return tree[v];
int tm = (tl + tr) / 2;
return min(query_min(2 * v, tl, tm, l, min(r, tm)), query_min(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
//查询最大值
int query_max(int v, int tl, int tr, int l, int r) {
if (l > r)
return INT_MIN;
if (l == tl && r == tr)
return tree[v];
int tm = (tl + tr) / 2;
return max(query_max(2 * v, tl, tm, l, min(r, tm)), query_max(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
};
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++)
cin >> arr[i];
SegmentTree st(n);
st.build(arr, 1, 0, n - 1);
int q, l, r;
cin >> q;
while (q--) {
cin >> l >> r;
printf("区间和：%d 区间最小值：%d 区间最大值：%d\n", st.query_sum(1, 0, n - 1, l, r), st.query_min(1, 0, n - 1, l, r), st.query_max(1, 0, n - 1, l, r));
}
return 0;
}
几组测试数据：
-
1
5
1 3 2 4 5
4
0 4
0 1
2 3
3 3
-
2
13
1 5 4 3 7 6 8 5 4 6 5 4 3
6
0 12
4 7
2 8
4 6
1 8
0 7
-
3
8
143 435 345 765 764 578 940 243
5
0 7
4 7
1 4
3 3
4 6
有帮助，赞一个