模板介绍
基础要求
-
线段树
-
能灵活运用 线段树
-
前缀和,差分
概念
- 可持久化:在某个历史版本上更改；查询某个历史版本上的值
引入
这道可持久化线段树的题 大概就是单点修改&单点查询
代码大致就是在线段树的基础上改变她存点的方式
以前
tree[k].l == k << 1
tree[k].r == k << 1 | 1
对于可持久化线段树
tree[k].l != k << 1
tree[k].r != k << 1 | 1
inline int tree_build(int k,int l,int r)
{
k = ++cnt;
每次这样来存点 但l和r仍然保留 表示一个递归和原序列位置的过程
if(l == r)
{
tree[k].val = seq[l];
return k;
}
int mid = l + r >> 1;
tree[k].l = tree_build(tree[k].l,l,mid);
tree[k].r = tree_build(tree[k].r,mid + 1,r);
return k;
}
大概酱紫
#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= (x)&&(x) <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0,f = 1;
char a = getchar();
while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
return x * f;
}
const int MAXN = 1e6 + 10;
int seq[MAXN],root[MAXN],cnt,tot;
struct node
{
int l,r,val;
}tree[MAXN * 13];
inline int tree_build(int k,int l,int r)
{
k = ++cnt;
if(l == r)
{
tree[k].val = seq[l];
return k;
}
int mid = l + r >> 1;
tree[k].l = tree_build(tree[k].l,l,mid);
tree[k].r = tree_build(tree[k].r,mid + 1,r);
return k;
}
inline int update(int k,int l,int r,int pos,int v)
{
tree[++cnt] = tree[k];
k = cnt;
if(l == r)
{
tree[k].val = v;
return k;
}
int mid = l + r >> 1;
if(pos <= mid) tree[k].l = update(tree[k].l,l,mid,pos,v);
else tree[k].r = update(tree[k].r,mid + 1,r,pos,v);
return k;
}
inline int query(int k,int pos,int l,int r)
{
if(l == r) return tree[k].val;
int mid = l + r >> 1;
if(pos <= mid) return query(tree[k].l,pos,l,mid);
return query(tree[k].r,pos,mid + 1,r);
}
int main()
{
int n = Read(1),m = Read(1);
for(reg i = 1;i <= n;i++)
seq[i] = Read(1);
root[tot] = tree_build(1,1,n);
while(m--)
{
int v = Read(1),sit = Read(1),loc = Read(1);
if(sit & 1)
{
int value = Read(1);
root[++tot] = update(root[v],1,n,loc,value);
} else {
int ans = query(root[v],loc,1,n);
root[++tot] = root[v];
printf("%d
",ans);
}
}
return 0;
}
真正的板子题
针对会主席树的同学
看看我写的思路 应该就可以秒懂了
建权值线段树
如图 每个点的权值为([a,b])的数值个数
样例输入
5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1
数据很大 (−(10^9)≤(a_i)≤(10^9))想到离散化
int len = unique(seq + 1,seq + 1 + n) - seq - 1;
for(reg i = 1;i <= n;i++)
int it = lower_bound(seq + 1,seq + 1 + len,past_a[i]) - seq;
(Firstly)
查询思路
很容易理解 对于一个询问([a,b])
我们先求([1,b])中有多少个数值
再求([1,a - 1])中的数值个数
每一个节点的权值对应相减
得到的就是([a,b])中的数值个数
因为我们建立的是权值线段树
所以一个节点(*p)
如果(k)（第(k)小值）≤ (*p->val)
向左子树查找
反之向右
直到(l == r)
找到了第(k)小值(hash)(离散化)后的值
离散化时 用一个下标(离散化)后的值对应 原值的数组
就可以输出了
(Secondly)
查询要点
我们先求([1,b])中有多少个数值
再求([1,a - 1])中的数值个数
每一个节点的权值对应相减
这个操作明显复杂且难以实现 时间复杂度也不能保证
我们便考虑每次(query)时传两个（同时做两个线段树的操作）
inline int query(int a,int b,int k,int l,int r)
{
if(l == r) return l;
int x = tree[tree[a].l].val - tree[tree[b].l].val;
int mid = l + r >> 1;
if(k <= x) return query(tree[a].l,tree[b].l,k,l,mid);
return query(tree[a].r,tree[b].r,k - x,mid + 1,r);
}
(Thirdly)
修改
最开始是空树
每次添点时把她当做一种新的历史状态
直接用主席树维护
(Code)
#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= (x)&&(x) <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0,f = 1;
char a = getchar();
while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
return x * f;
}
const int MAXN = 2e5 + 10;
int seq[MAXN],root[MAXN << 5],past_a[MAXN],cnt,tot;
struct node
{
int l,r,val;
}tree[MAXN << 5];
inline int tree_build(int k,int l,int r)
{
k = ++cnt;
if(l == r) return k;
int mid = l + r >> 1;
tree[k].l = tree_build(tree[k].l,l,mid);
tree[k].r = tree_build(tree[k].r,mid + 1,r);
return k;
}
inline int update(int k,int l,int r,int pos)
{
tree[++cnt] = tree[k];
k = cnt;
tree[k].val++;
if(l == r) return k;
int mid = l + r >> 1;
if(pos <= mid) tree[k].l = update(tree[k].l,l,mid,pos);
else tree[k].r = update(tree[k].r,mid + 1,r,pos);
return k;
}
inline int query(int a,int b,int k,int l,int r)
{
if(l == r) return l;
int x = tree[tree[a].l].val - tree[tree[b].l].val;
int mid = l + r >> 1;
if(k <= x) return query(tree[a].l,tree[b].l,k,l,mid);
return query(tree[a].r,tree[b].r,k - x,mid + 1,r);
}
int main()
{
int n = Read(1),m = Read(1);
for(reg i = 1;i <= n;i++)
past_a[i] = seq[i] = Read(1);
sort(seq + 1,seq + 1 + n);
int len = unique(seq + 1,seq + 1 + n) - seq - 1;
root[tot] = tree_build(1,1,len);
for(reg i = 1;i <= n;i++)
{
int it = lower_bound(seq + 1,seq + 1 + len,past_a[i]) - seq;
root[i] = update(root[i - 1],1,len,it);
}
while(m--)
{
int l = Read(1),r = Read(1),k = Read(1);
int ans = query(root[r],root[l - 1],k,1,len);
printf("%d
",seq[ans]);
}
return 0;
}
习题
(Code)
#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= (x)&&(x) <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0,f = 1;
char a = getchar();
while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
return x * f;
}
const int MAXN = 1e5 + 10;
int seq[MAXN],root[MAXN],cnt,tot;
typedef long long ll;
struct node
{
int l,r;
ll val,tag;
}tree[MAXN << 6];
inline int tree_build(int k,int l,int r)
{
k = ++cnt,tree[k].tag = 0;
if(l == r) {tree[k].val = seq[l];return k;}
int mid = l + r >> 1;
tree[k].l = tree_build(tree[k].l,l,mid);
tree[k].r = tree_build(tree[k].r,mid + 1,r);
tree[k].val = tree[tree[k].l].val + tree[tree[k].r].val;
return k;
}
inline int update(int k,int l,int r,int L,int R,ll v)
{
tree[++cnt] = tree[k],k = cnt;
tree[k].val += (R - L + 1) * v;
if(L == l&&r == R) {tree[k].tag += v;return k;}
int mid = l + r >> 1;
if(R <= mid) tree[k].l = update(tree[k].l,l,mid,L,R,v);
else if(mid < L) tree[k].r = update(tree[k].r,mid + 1,r,L,R,v);
else tree[k].l = update(tree[k].l,l,mid,L,mid,v),tree[k].r = update(tree[k].r,mid + 1,r,mid + 1,R,v);
return k;
}
inline ll query(int k,int l,int r,int L,int R,ll tot)
{
if(l == L&&r == R) return tree[k].val + (r - l + 1) * tot;
int mid = l + r >> 1;
if(R <= mid) return query(tree[k].l,l,mid,L,R,tot + tree[k].tag);
if(mid < L) return query(tree[k].r,mid + 1,r,L,R,tot + tree[k].tag);
ll k1 = query(tree[k].l,l,mid,L,mid,tot + tree[k].tag),k2 = query(tree[k].r,mid + 1,r,mid + 1,R,tot + tree[k].tag);
return k1 + k2;
}
int main()
{
int n = Read(1),m = Read(1),pre = 0;
for(reg i = 1;i <= n;i++)
seq[i] = Read(1);
root[tot] = tree_build(1,1,n);
while(m--)
{
char sit = getchar();
while(sit != 'C'&&sit != 'H'&&sit != 'B'&&sit != 'Q') sit = getchar();
if(sit == 'C')
{
int l = Read(1),r = Read(1),d = Read(1);
root[pre + 1] = update(root[pre],1,n,l,r,d * 1ll);
pre++;
}
if(sit == 'Q')
{
int l = Read(1),r = Read(1);
ll ans = query(root[pre],1,n,l,r,0ll);
printf("%lld
",ans);
}
if(sit == 'H')
{
int l = Read(1),r = Read(1),t = Read(1);
ll ans = query(root[t],1,n,l,r,0ll);
printf("%lld
",ans);
}
if(sit == 'B') pre = Read(1);
}
return 0;
}