主席树求区间第K小模板

2024-03-05 19:04
文章标签 模板 区间 主席 树求

本文主要是介绍主席树求区间第K小模板,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

主席树(President Tree)是一种用于解决区间查询和修改问题的数据结构,通常用于静态区间问题(即查询和修改操作在构建结构之后不再发生变化)。主席树可以高效地处理诸如区间和、区间最值等问题。

主席树的实现原理:

  1. 基本思想:主席树是一种基于分治思想的数据结构,它将原始序列按照每个位置的取值范围进行离散化,然后构建出一棵持久化线段树(Persistent Segment Tree)。

  2. 持久化线段树:持久化线段树是线段树的一种扩展,它能够记录每次修改后的线段树版本,而不是像传统线段树那样每次都覆盖更新。通过这种方式,我们可以在保留历史版本的基础上进行有效的区间查询。

  3. 构建过程:首先对原始序列进行排序和离散化,然后根据每个位置的取值范围构建出持久化线段树。在构建过程中,每棵线段树都会继承前一棵线段树的所有信息,并根据具体的修改操作进行更新。

  4. 查询操作:利用持久化线段树,可以高效地进行区间查询操作,例如区间求和、区间最值等。

优点和应用:

  1. 主席树适用于静态区间问题,即查询和修改操作在构建结构之后不再发生变化的场景。
  2. 它能够高效地处理区间查询和修改问题,例如区间和、区间最值等。

总的来说,主席树是一种用于解决静态区间查询和修改问题的数据结构,通过离散化和持久化线段树的方式,能够高效地处理各种区间操作。希望这些信息能帮助你理解主席树的基本原理和应用场景。

题目

给定n个数,q次询问,每次求区间 [ l , r ] 中从小到大排序后第 k 个数。
1 <= n <= 100 000, 1 <= q <= 5 000,1 <=l <=r<= n, 1 <= k <= j - i + 1

示例

Input
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Output
5
6
3

Code

#include <iostream>
#include<cstdio>
#include<algorithm>
#define midd (l+r)/2
using namespace std;
typedef long long ll;
const int N = 200010;
int n, q, sz, cnt = 0;
int a[N], b[N], T[N];//a为原数组,b为排序离散化数组,T[i]为(值)[1,i]的根节点
int sum[N<<5], L[N<<5], R[N<<5];inline int build(int l, int r)
{int rt = ++ cnt;sum[rt] = 0;if (l < r){L[rt] = build(l, midd);R[rt] = build(midd+1, r);}return rt;
}inline int update(int pre, int l, int r, int x)
{int rt = ++ cnt;L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre]+1;if (l < r){if (x <= midd) L[rt] = update(L[pre], l, midd, x);else R[rt] = update(R[pre], midd+1, r, x);}return rt;
}inline int query(int u, int v, int l, int r, int k)//返回下标,即<=k个数
{if (l >= r) return l;int x = sum[L[v]] - sum[L[u]];if (x >= k) return query(L[u], L[v], l, midd, k);else return query(R[u], R[v], midd+1, r, k-x);
}int main()
{while(scanf("%d%d", &n, &q)!=EOF){cnt=0;for (int i = 1; i <= n; i ++){scanf("%d", &a[i]);b[i] = a[i];}sort(b+1, b+1+n);sz = unique(b+1, b+1+n)-b-1;T[0] = build(1, sz);for (int i = 1; i <= n; i ++){int t = lower_bound(b+1, b+1+sz, a[i])-b;T[i] = update(T[i-1], 1, sz, t);}while (q --){int l, r, k;scanf("%d%d%d", &l, &r ,&k);// k= r-l+1-k+1;//求第k大时改一下就行int idx=query(T[l-1], T[r], 1, sz, k);int ans=b[idx];printf("%d\n",ans);}}return 0;
}

通过构建持久化线段树,实现了区间查询和修改操作。可以通过调用 update 函数更新结点信息,通过调用 query 函数查询区间内第 k 小的元素。

这篇关于主席树求区间第K小模板的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/777502

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

poj 2104 and hdu 2665 划分树模板入门题

题意: 给一个数组n(1e5)个数,给一个范围(fr, to, k),求这个范围中第k大的数。 解析: 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码: poj 2104: #include <iostream>#include <cstdio>#include <cstdlib>#include <al

最大流、 最小费用最大流终极版模板

最大流  const int inf = 1000000000 ;const int maxn = 20000 , maxm = 500000 ;struct Edge{int v , f ,next ;Edge(){}Edge(int _v , int _f , int _next):v(_v) ,f(_f),next(_next){}};int sourse , mee

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead