Notes d'apprentissage ACM: arbre de segment persistant

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