#创作计划#个性线段树模版

userId_undefined
只喜欢AC&人畜无害滴卡皮巴拉~
出道萌新时间刺客循环·循环打卡人模拟·模拟练习生分支·分支解题者GESP3级

2026-03-07 10:54:57

发布于：浙江

266阅读
0回复
0点赞

本篇只讲简单的线段树，仅建树、求区间最大/最小值。

其他大佬的模版都比较长，不易理解，读起来也比较费劲，今天分享一款比较简短的蒟蒻式模版
废话不多说，有点二叉树基础的狗友都知道：


（仅节点编码）
那么我们的模版也会根据这个小知识点进行扩张

1.建树

#include<bits/stdc++.h>
using namespace std;
int tree[405];
int a[105];
void build(int root,int l,int r)
{
	if (l<r) return tree[root]=a[l];
	int mid=(l+r)/2;
	return tree[root]=min(build(root*2,l,mid),build(root*2+1,mid+1,r));//最小值 
	//return tree[root]=max(build(root*2,l,mid),build(root*2+1,mid+1,r));//最大值
}
int main()
{
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	return 0;
}

这就是建树，其中思路与归并排序类似，递归从根节点开始分别向其左子树与其右子树遍历建树
tree[i]tree[i]表示节点编号为ii的线段树节点的存值


橙色为原数组区间，红色为节点存值，黑色为节点编号。
本图以最大值建树为例
即节点存的值是其左子树与右子树中的最大值
举个栗子：节点1存的就是区间[1,2][1,2]与区间[3,4][3,4]合并所得的最大值

模拟过程

1.递归区间[1,4][1,4]
条件不成立，递归结果max([1,2],[3,4])max([1,2],[3,4])
2.递归区间[1,2][1,2]
条件不成立，递归结果max([1,1],[2,2])max([1,1],[2,2])
3.两个子区间条件成立，回溯至2
4.结果为[2,2][2,2]，回溯至1
5.递归区间[3,4][3,4]
条件不成立，递归结果max([3,3],[4,4])max([3,3],[4,4])
6.两个子区间条件成立，回溯至5
7.结果为[4,4][4,4]，回溯至1
8.结果为[1,2][1,2]，递归结束，建树成功

好了，咱们已经获得了一棵优美的维护最大值的线段树了，接下来就是查询了

2.查询

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005];
int tree[4000005];//顺序存储法 
int built(int root,int l,int r)//返回[l,r]的最大值 
{
    if (l==r) return tree[root]=a[l];//维护叶节点 
    int mid=(l+r)/2;
    return tree[root]=max(built(root*2,l,mid),built(root*2+1,mid+1,r));
}
int query(int root,int l,int r,int ql,int qr)//返回[ql,qr]的最大值 
{
    if (qr<l||r<ql) return INT_MIN;//要求最大值返回最小值，反之亦然
    if (ql<=l&&r<=qr) return tree[root];//叶子节点
    int mid=(l+r)/2;
    return max(query(root*2,l,mid,ql,qr),query(root*2+1,mid+1,r,ql,qr));//维护最大值
}
int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    built(1,1,n);
    while(m--)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d\n",query(1,1,n, x,y));//查询区间
    }
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 47

热门讨论