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 sectionkUne 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 estiNombre d'éléments pour,posC'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 dekGrande 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 estkGrand,À droite, moins,Si c'est lakPetit 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.posLe 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 arbreO(nlogn)

L'enquête estO(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,De1Démarrer le stockage du noeud racine

struct Node{
   int lc,rc,sum; //Fils de gauche fils de droite et valeursum
}hjt[maxn*32] //L'espace est généralement ouvert32C'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 parKPetit

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.iVersion 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 lerank
{
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,rIndique l'intervalle actuel,x,yReprésente les anciens et les nouveaux arbres,kPour trouver dans cette sectionkPetit
if (l == r)
{
return l;    //Si vous le trouvez, retournez directement à la pagekPetite valeurl
}
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++)
{//NoyNombre d'arbres etx-1Mauvais nombre d'arbres,Pour découvrir[x,y]Section parkPetite 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

ACMNotes d'étude: Autre article Afghanistan Afghanistan

  1. [Notes d'étude] Arbre de segment persistant&amp;Arbre du Président

    Tout le monde sait, L'arborescence des segments de ligne est une structure de données très facile à utiliser et à écrire , Donc,, Nos compétences d'avant - garde d'aujourd'hui :Arbre de segment. Et pourtant, Qu'est - ce que la durabilité? ? Ne vous pressez pas., Pas à pas. ... step 1 Tout d'abord,, Un modèle simplifié : Une longueur donnée est\ ...

  2. [Notes d'étude]Structures de données durables——Tableau、Ensemble de recherche、Arbre d'équilibre、TrieArbre

    Durable:Prise en charge de la requête et de la modification de la version historique Tableau persistant L'arbre du Président peut le faire.. [Modèle]Tableau persistant(Arbre de segment persistant/Arbre d'équilibre) Persistance et recherche d'ensembles Persistance et recherche d'ensembles L'arbre du Président peut le faire.. Pour fusionner par rang.(Compression du chemin par construction ...

  3. HDU 5820 (Arbre de segment persistant)

    Problem Lights (HDU 5820) Objet Dans une taille de 50000*50000 Dans le rectangle de ,Oui.n Feux de rue .(n<=500000) Demandez s'il y a une route entre chaque paire de lampadaires , Faire la longueur |x1 ...

  4. HDU 4348 To the moon Arbre de segment persistant, Mise à jour de l'intervalle avec TIMESTAMP , Somme des intervalles

    To the moonTime Limit: 20 Sec Memory Limit: 256 MB Lien thématique http://acm.hust.edu.cn/vjudge/contest/view.a ...

  5. HDU 5919 Sequence II(Arbre de segment persistant)

    [Liens vers les sujets]http://acm.hdu.edu.cn/showproblem.php?pid=5919 [Objet] Donne une séquence de nombres , Dans la colonne par requête , Médiane de l'indice des éléments non lourds de l'intervalle . Action de requête forcée en ligne . [ ...

  6. Aubergiste 38229.Distance on the tree-1. Division de la chaîne des arbres ( Droits latéraux )+Arbre de segment persistant( Intervalle inférieur ou égal à k Nombre de )+Discrétisation+ Traitement hors ligne or 2. Arbre No. kGrand(Arbre du Président)+Deux points+Discrétisation+Demandes de renseignements en ligne (The Preliminary Contest for ICPC China Nanchang National Invitational Concours en ligne sur invitation de Nanchang )

    Distance on the tree DSM(Data Structure Master) once learned about tree when he was preparing for NO ...

  7. bzoj 3673&amp;3674 Persistance et recherche d'ensembles&amp;Version améliorée(Arbre de segment persistant+Fusion heuristique)

    CCZIn2015Année8Mois25 C'est la fin des trois premières vacances d'été. %%% J'ai appris une autre méthode heuristique de fusion , Fusionner par rang , C'est - à - dire fusionner par profondeur d'arbre , En fait, c'est la même chose que la taille d'un arbre. ,Mais les sentiments( Au moins sur ce sujet. )C'est mieux. ...

  8. HDU 4417.Super Mario-Arbre de segment persistant( Intervalle non modifié inférieur ou égal à H Nombre de )

    Super Mario Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total ...

  9. La vallée de lo——P3919 【Modèle】Tableau persistant(Arbre de segment persistant/Arbre d'équilibre)

    P3919 [Modèle]Tableau persistant(Arbre de segment persistant/Arbre d'équilibre) Contexte du sujet UPDATE : Le dernier point a été agrandi. Le titre est le titre. Avec un tableau persistant , Permet de nombreuses fonctions de persistance dérivées (Par exemple:Persistance et recherche d'ensembles ...

  10. 【NOIP2017】 En rang. 【Arbre de segment persistant】

    Liens vers les sujets Description du sujet Sylvia  C'est une fille qui aime étudier. . Il y a quelque temps,Sylvia  A participé à l'entraînement militaire de l'école .Tout le monde sait, Il faut se tenir debout pendant l'entraînement. . Sylvia Dans la matrice n×mn×mÉtudiants, Le nombre de lignes de la matrice est  n ...

Recommandation aléatoire

  1. Cadre d'ordonnancement des tâches Quartz Notes d'étude(Trois) -- CronExpression (Réimpression)

    Les deux premiers articles parlent de déclencheurs simples (SimpleTrigger) , SimpleTrigger Ne peut gérer que des événements simples , Si vous voulez être flexible dans le déclenchement des tâches , On va sortir. CronTrigger C'est un homme important. . Cro ...

  2. openerp Questions fréquemment posées OpenERP Où conserver les accessoires ?(Réimpression)

    OpenERP Où conserver les accessoires ? Adresse originale:http://cn.openerp.cn/where_to_store_attachement_in_openerp_7/ On sait. OpenERP Chaque intérieur ...

  3. Un par jour LinuxLes ordres(05)--rmLes ordres

    Depuis que j'ai appris à utiliser mkdir Après la création du Répertoire , Il n'y a qu'un tas de répertoires vides dans tout le système. ,Non.~ Aujourd'hui, apprenons à nettoyer ces répertoires vides. --rmLes ordres, La fonction de cette commande est de supprimer un ou plusieurs fichiers ou répertoires d'un répertoire , Il peut également placer un répertoire ...

  4. PyCharmConfigurationautopep8, Formatage automatique PythonCode

    1. À propos dePEP 8 PEP 8,Style Guide for Python Code,- Oui.Python Contrat officiel de codage de lancement , Principalement pour garantir Python Le style de codage est cohérent , Améliorer la lisibilité du Code . Adresse du site officiel:h ...

  5. AdoptiondjangoDerest-framework……(CBV)

    Pourquoi ne pas utiliserFBV,Parce queCBV Très réutilisable Prenons un exemple. : from django.views.generic.base import View from django.http import Http ...

  6. swiper Problèmes de réglage de la hauteur des composants

    1.swiper Lorsque les composants sont utilisés directement , .content>swiper{height:100%} Ça ne marche pas. . La bonne chose à faire est: swiper{ height: 100vh; } // Ou < ...

  7. RedHat6.5 Installation d'une seule machine flume1.6

    Numéro de version: RedHat6.5   JDK1.8   apache-flume-1.6.0 1.apache-flume-1.6.0-bin.tar.gz Télécharger Adresse de téléchargement du site officiel:http://archiv ...

  8. 20172325 2017-2018-2 《JavaProgrammation》 Résumé de la semaine 10

    20172325 2017-2018-2 <JavaProgrammation> Résumé de la semaine 10 Résumé du contenu des manuels scolaires 1. Collections et structures de données Une collection est un objet Les collections peuvent être divisées en deux types selon le type d'enregistrement : (1) Ensemble isomorphe :Seulement ...

  9. unity3d Aperçu des matériaux ---- shader

    Notes d'étude:      Aperçu des matériaux :   Les objets se présentent devant nous, à l'exception de la forme. ,Y compris“ Couleur naturelle ”Et“Texture”( Texture et propriétés optiques ). Quelle couleur la couleur naturelle donne à la surface de l'objet , La texture détermine le matériau utilisé. . Logiciel de modélisation 3D ...

  10. Python Programmation parallèle (XIV.):Programmation asynchrone

    1.Concepts de base En plus des modèles séquentiels et parallèles , Et des modèles asynchrones , C'est la base d'un modèle axé sur les événements . Le modèle d'exécution des activités asynchrones ne peut avoir qu'un seul flux de contrôle principal , Capable de fonctionner dans un système à noyau unique et un système à noyau multiple . Dans un modèle asynchrone d'exécution simultanée , De nombreuses tâches ...