Notes d'apprentissage ACM: arbre de segment persistant

Linno 2021-08-19 23:51:12 阅读数:289

notes apprentissage acm arbre segment
title : Arbre de segment persistant
date : 2021-8-18
tags : Structure des données,ACM

 

Arbre de segment persistant

Peut être utilisé pour résoudre le problème de l'état historique de stockage de l'arbre de segment.

Après un seul point de modification,L'arbre de segment n'a quelogn- Oui.(Une chaîne)Le noeud a été modifié,Nous pouvons partager les noeuds entre l'arbre modifié et l'arbre avant,.Gagner du temps et de l'espace.

Avant d'étudier,Nous introduisons d'abord trois connaissances préalables:Discrétisation、Point d'ouverture dynamique,Arbre des segments de poids.

 

Discrétisation

Pour une large gamme de données,Il suffit de noter les points clés,Notez - le.rank,Pour réduire les données à un niveau acceptable,Pour créer un arbre de segment ou une autre structure de données pour résoudre le problème.

Étapes spécifiques

(1)Ajouter tous les paramètres au tableau auxiliaire; (2)Trier par coordonnées du plus petit au plus grand; (3)Poids mort; (4)Dispersion des données,AvechsLe tableau enregistre le classement des paramètres au lieu d'un nombre spécifique

vector<int>vt;
for(int i=1;i<=n;i++){
   cin>>a[i];
   vt.push(a[i]); //Ajouter le contenant auxiliaire
}
sort(vt.begin(),vt.end());//Trier
vt.erase(unique(vt.begin(),vt.end()),vt.end()); //Poids mort
for(int i=0;i<vt.size();i++){
   hs[vt[i]]=++tot; //Stocké sousrank
}

 

Point d'ouverture dynamique

L'arbre dynamique à points ouverts permet d'éviter la discrétisation .

Si la plage de valeurs de l'arbre des segments de poids est grande , La discrétisation est difficile , Vous pouvez utiliser la technique du point d'ouverture dynamique .

L'étape de construction de l'arbre a été omise , Au lieu de cela, ajoutez des noeuds aux opérations spécifiques .

 

Arbre des segments de poids

Le noeud foliaire de l'arbre segment contient le nombre de valeurs actuelles .

Chaque noeud stocke les extrémités gauche et droite de l'intervalle et le nombre de noeuds de l'intervalle dans lequel il se trouve .

Comme la plage de valeurs est généralement grande , En général, l'espace est optimisé avec des stratégies telles que la discrétisation ou l'ouverture dynamique .

Application

Trouver la section k Une grande valeur

Demander le classement d'un certain nombre

Demander le tri de l'ensemble du tableau

Avant et après la requête

Modification en un seul point
void update(int node,int start,int end,int pos){
   if(start==end) tr[node]++;
   else{
       int mid=start+end>>1;
       if(pos<=mid) update(node<<1,start,mid,pos);
       else update(node<<1|1,mid+1,end,pos);
  }
}//tr[i] Indique que la valeur est i Nombre d'éléments pour ,pos C'est l'endroit à trouver
Nombre d'occurrences dans l'intervalle de requête
int query(int node,int start,int end,int ql,int qr){
   if(start==ql&&end==qr) return tr[node];
   int mid=start+end>>1;
   if(qr<=mid) return query(node<<1,start,mid,ql,qr);
   else if(ql>mid) return query(node<<1|1,mid+1,end,ql,qr);
   else return query(node<<1,start,mid,ql,qr)+query(node<<1|1,mid+1,end,ql,qr);
}// Il en va de même pour les requêtes en un seul point
Rechercher tous les numéros de k Grande valeur
int kth(int node,int start,int end,int k){
   if(start==end) return start;
   int mid=start+end>>1;
   int s1=tr[node<<1],s2=tree[node<<1|1];
   if(k<=s2) return kth(node<<2|1,mid+1,end,k);
   else return kth(node<<1,start,mid,k-s2);
} // L'attention est kGrand, À droite, moins , Si c'est la k Petit moins gauche
Recherche de préfixes ( Après la même chose )
int findpre(int node,int start,int end){ // Trouvez le plus grand 
   if(start==end) return start; // Retour direct trouvé
   int mid=start+end>>1;
   if(t[node<<1|1]) return findpre(node<<1|1,mid+1,end);
   return findpre(node<<1,start,mid);
}

int pre(int node,int l,int r,int pos){ //S'il te plaît.pos Le précurseur de
   if(r<pos){ // À l'extrême droite
       if(t[node]) return findpre(node,l,r);
       return 0;
  }
   int mid=l+r>>1,res;
   if(mid+1<pos&&t[node<<1|1]&& (res=pre(node<<1|1,mid+1,r,pos))) return res; // Cherchez dans la section droite
   return pre(node<<1,l,mid,pos);  // Cherchez dans la Section de gauche
}

 

 

Arbre de segment persistant

Analyse de la complexité

Construire un arbre O(nlogn)

L'enquête est O(logn)

Complexité spatialeO(nlognlogn).

 

L'idée centrale

Créé sous forme de préfixe et de , Forme de stockage basée sur un point d'ouverture dynamique .

Entre deux arbres de segment de ligne sont réductibles ( Chaque noeud correspond à une soustraction ).

 

Stockage

hjt[0]Agir commeNULL,De1 Démarrer le stockage du noeud racine

struct Node{
   int lc,rc,sum; // Fils de gauche fils de droite et valeur sum
}hjt[maxn*32] // L'espace est généralement ouvert 32C'est tout.
int cnt,root[maxn];// Compteur de pool de mémoire et numéro de noeud racine
Insérer

Ne change pas l'arbre d'origine , C'est le nouveau noeud racine ouvert , Et il descend

void insert(inr cur,int pre.int pos,int l,int r){
   if(l==r){ // Trouver ce point , Valeur actuelle du point de version +1
       t[cur].v=t[pre].v+1;
       return;
  }
   int mid=l+r>>1;
   if(pos<=mid){
       t[cur].lc=++e;
       t[cur].rc=t[pre].rc;
       insert(t[cur].lc,t[pre].lc,pos,l,mid);
  }else{
       t[cur].rc=++e;
       t[cur].lc=t[pre].lc;
       insert(t[cur].rc,t[pre].rc,pos,mid+1,r);
  }
   t[cur].v=t[t[cur].lc].v+t[t[cur].rc].v; //pushup
}
Demander l'opération

Essentiellement identique à l'arbre des segments de poids , Il suffit de faire la différence entre les intervalles .

int query(int l,int r,int x,int y,int k){
if (l == r){
return l;
  }
int mid=(l+r)/2;
int sum=tr[tr[y].l].sum-tr[tr[x].l].sum;
if(sum >= k){
return query(l,mid,tr[x].l,tr[y].l,k);
}
else{
       return query(mid+1,r,tr[x].r,tr[y].r,k-sum);
}
}
Section par KPetit

luoguP3834 【Modèle】Arbre de segment persistant 2(Arbre du Président)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 7;

int n, m, cnt, rt[maxn], a[maxn], x, y, k;
//a[i] C'est la séquence originale ,rt[i]Oui.i Version de l'arbre du Président

struct node
{
int l, r, sum; // L'extrémité gauche de l'arbre 、 Côté droit et nombre d'éléments
} tr[maxn * 32];

vector<int> vt; // Récipient auxiliaire

void read(int &data)  // Optimisation de la lecture rapide
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
{
f = f * -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
data = x * f;
}

int getid(int x)  // Renvoie le rank
{
return lower_bound(vt.begin(), vt.end(), x) - vt.begin() + 1;
}

void insert(int l, int r, int &x, int y, int pos)
{ // Chaque fois que vous modifiez ou insérez , Créer un nouveau noeud racine , Et Récursivement vers le bas pour créer un nouveau noeud
tr[++cnt] = tr[y];
tr[cnt].sum++;  // Nombre d'éléments régionaux +1
x = cnt; // Pointez l'adresse originale de l'arbre vers l'arbre courant
if (l == r)
{ // C'est déjà une feuille ,Retour
return;
}
int mid = (l + r) / 2;
if (mid >= pos)
{  // Insérer dans le Sous - arbre gauche
insert(l, mid, tr[x].l, tr[y].l, pos);
}
else
{  // Insérer dans le Sous - arbre droit
insert(mid + 1, r, tr[x].r, tr[y].r, pos);  
}
}

int query(int l, int r, int x, int y, int k)
{ //l,r Indique l'intervalle actuel ,x,y Représente les anciens et les nouveaux arbres ,k Pour trouver dans cette section kPetit
if (l == r)
{
return l;    // Si vous le trouvez, retournez directement à la page k Petite valeur l
}
int mid = (l + r) / 2;
int sum = tr[tr[y].l].sum - tr[tr[x].l].sum;
// Soustraction du sous - arbre gauche , La différence est le nombre de différences à gauche entre les deux versions
if (sum >= k)
{  // Résultat supérieur ou égal à k, Demandez au sous - arbre gauche
return query(l, mid, tr[x].l, tr[y].l, k);
}
else
{  // Sinon, trouvez le Sous - arbre droit. k-sumPetit nombre
return query(mid + 1, r, tr[x].r, tr[y].r, k - sum);
}
}

signed main()
{
read(n);
read(m);
for (int i = 1; i <= n; i++)
{
read(a[i]);
vt.push_back(a[i]); // Conteneur auxiliaire pour la discrétisation
}
sort(vt.begin(), vt.end()); //Trier
vt.erase(unique(vt.begin(), vt.end()), vt.end()); //Poids mort
for (int i = 1; i <= n; i++)
{  // Chaque insertion crée un nouvel arbre à partir du noeud racine ( Pour former une chaîne )
insert(1, n, rt[i], rt[i - 1], getid(a[i]));
}

for (int i = 1; i <= m; i++)
{//Noy Nombre d'arbres et x-1 Mauvais nombre d'arbres , Pour découvrir [x,y] Section par k Petite valeur
read(x);
read(y);
read(k);
printf("%d\n", vt[query(1, n, rt[x - 1], rt[y], k) - 1]);

}
return 0;
}

 

 

Références

https://www.cnblogs.com/young-children/p/11787490.html

https://www.cnblogs.com/young-children/p/11787493.html

https://blog.csdn.net/ModestCoder_/article/details/90107874

https://blog.csdn.net/a1351937368/article/details/78884465

Copyright:Cet article est[Linno]Établi,Veuillez apporter le lien original pour réimprimer,remercier。 https://fra.fheadline.com/2021/08/20210819235106552r.html