L'arbre de segments (Segment Tree) est une structure de données avancée, basée sur le principe de diviser pour régner. Il s'agit d'une structure arborescente binaire principalement conçue pour résoudre des problèmes d'intervalle ou de plage. Cette structure permet de maintenir des variables qui satisfont la propriété d'associativité (comme le maximum, le minimum, la somme ou l'opérateur XOR) sur des séquences, avec une complexité temporelle de \\(O(\\log n)\\) par opération. C'est une structure de données extrêmement puissante, avec de nombreuses applications et extensions.
1. Concepts de Base et Opérations
Un arbre de segments est essentiellement un arbre binaire possédant les caractéristiques suivantes :
- Chaque nœud de l'arbre représente un intervalle.
- Le nœud racine est unique et représente l'intégralité de la plage surveillée (par exemple, \\(\[1, N\]\\)).
- Chaque nœud feuille correspond à un intervalle unitaire de longueur \\(1\\), de la forme \\(\[x, x\]\\).
- Pour tout nœud interne représentant l'intervalle \\(\[l, r\]\\), son enfant gauche représente \\(\[l, mid\]\\) et son enfant droit représente \\(\[mid + 1, r\]\\), où \\(mid = \\lfloor\\frac{l + r}{2}\\rfloor\\). Cette division garantit une couverture complète et sans chevauchement de l'intervalle.
Visuellement, à l'exception du dernier niveau, un arbre de segments est un arbre binaire complet. Sa profondeur est en \\(O(\\log n)\\). Nous pouvons donc numéroter les nœuds de manière similaire aux tas binaires :
- Le nœud racine est numéroté \\(1\\).
- L'enfant gauche d'un nœud numéroté \\(p\\) est \\(2p\\), et son enfant droit est \\(2p + 1\\).
Avec cette convention de numérotation, les informations des nœuds peuvent être stockées dans un tableau. Il est important de noter que pour un tableau de \\(N\\) éléments, l'arbre de segments peut nécessiter un tableau de taille allant jusqu'à \\(4N\\) pour éviter tout débordement, notamment en raison de l'espace potentiel inutilisé au dernier niveau.
struct NoeudSegment {
int debut, fin; // Intervalle [debut, fin] représenté par le nœud
long long valeur; // Valeur agrégée (ex: somme, max) pour cet intervalle
};
NoeudSegment arbre[N_MAX * 4]; // N_MAX est la taille maximale du tableau d'origine
Dans les exemples suivants, nous utiliserons la recherche du maximum dans un intervalle comme opération agrégée.
Construction de l'Arbre
La construction de l'arbre se fait de manière récursive, en suivant la structure binaire définie précédemment. On commence par la racine et on divise les intervalles jusqu'aux feuilles.
void construire(int indexNoeud, int debutIntervalle, int finIntervalle, const long long tableauOriginal[]) {
arbre[indexNoeud].debut = debutIntervalle;
arbre[indexNoeud].fin = finIntervalle;
if (debutIntervalle == finIntervalle) { // Nœud feuille
arbre[indexNoeud].valeur = tableauOriginal[debutIntervalle];
return;
}
int milieu = debutIntervalle + (finIntervalle - debutIntervalle) / 2; // Calcul robuste du milieu
construire(2 * indexNoeud, debutIntervalle, milieu, tableauOriginal); // Construction du sous-arbre gauche
construire(2 * indexNoeud + 1, milieu + 1, finIntervalle, tableauOriginal); // Construction du sous-arbre droit
// Remonter l'information : le max du parent est le max de ses enfants
arbre[indexNoeud].valeur = std::max(arbre[2 * indexNoeud].valeur, arbre[2 * indexNoeud + 1].valeur);
}
Modification Ponctuelle
Une modification ponctuelle, telle que la mise à jour de la valeur \\(A\[x\]\\) à \\(v\\), est effectuée en descendant récursivement l'arbre à partir de la racine. Une fois le nœud feuille représentant \\(\[x,x\]\\) trouvé, sa valeur est mise à jour. Lors de la remontée de la récursion, les nœuds parents intègrent les nouvelles informations de leurs enfants.
void mettreAJourPoint(int indexNoeud, int cible, long long nouvelleValeur) {
// Si nous sommes au nœud feuille correspondant à la cible
if (arbre[indexNoeud].debut == arbre[indexNoeud].fin) {
arbre[indexNoeud].valeur = nouvelleValeur;
return;
}
int milieu = arbre[indexNoeud].debut + (arbre[indexNoeud].fin - arbre[indexNoeud].debut) / 2;
if (cible <= milieu) {
mettreAJourPoint(2 * indexNoeud, cible, nouvelleValeur); // Descendre à gauche
} else {
mettreAJourPoint(2 * indexNoeud + 1, cible, nouvelleValeur); // Descendre à droite
}
// Remonter l'information après la mise à jour des enfants
arbre[indexNoeud].valeur = std::max(arbre[2 * indexNoeud].valeur, arbre[2 * indexNoeud + 1].valeur);
}
// Appel initial : mettreAJourPoint(1, x, v);
Cete opération a une complexité temporelle de \\(O(\\log n)\\).
Note : Bien que l'arbre de segments puisse effectuer des modifications ponctuelles, les arbres de Fenwick (ou BIT) sont souvent préférés pour cette tâche en raison de leurs constantes plus faibles. Cependant, dans des scénarios où l'arbre de segments est déjà utilisé pour d'autres opérations complexes sur des intervalles, il est logique de l'utiliser aussi pour les modifications ponctuelles. Une version itérative de la modification ponctuelle, qui évite la récursion en utilisant un tableau d'identifiants de feuilles et en remontant de manière itérative, peut offrir une meilleure performance en pratique, bien que la complexité asymptotique reste \\(O(\\log n)\\).
Requête d'Intervalle
Pour interroger une valeur (par exemple, le maximum) sur un intervalle \\(\[L, R\]\\), on procède récursivement depuis la racine. Le processus est le suivant :
- Si l'intervalle du nœud actuel est entièrement contenu dans la plage de requête \\(\[L, R\]\\), la valeur agrégée du nœud est directement retournée.
- Sinon, si l'intervalle de requête \\(\[L, R\]\\) chevauche l'enfant gauche, une requête récursive est effectuée sur l'enfant gauche.
- De même, si \\(\[L, R\]\\) chevauche l'enfant droit, une requête récursive est effectuée sur l'enfant droit.
- Les résultats des requêtes sur les enfants sont combinés pour obtenir le résultat final.
long long interrogerIntervalle(int indexNoeud, int debutRequete, int finRequete) {
// Si l'intervalle du nœud est entièrement inclus dans la plage de requête
if (debutRequete <= arbre[indexNoeud].debut && finRequete >= arbre[indexNoeud].fin) {
return arbre[indexNoeud].valeur;
}
long long resultat = -2e18; // Initialiser avec une valeur très petite pour le maximum
int milieu = arbre[indexNoeud].debut + (arbre[indexNoeud].fin - arbre[indexNoeud].debut) / 2;
// Si la plage de requête chevauche l'enfant gauche
if (debutRequete <= milieu) {
resultat = std::max(resultat, interrogerIntervalle(2 * indexNoeud, debutRequete, finRequete));
}
// Si la plage de requête chevauche l'enfant droit
if (finRequete > milieu) {
resultat = std::max(resultat, interrogerIntervalle(2 * indexNoeud + 1, debutRequete, finRequete));
}
return resultat;
}
Ce processus de requête décompose la plage demandée en \\(O(\\log n)\\) nœuds distincts de l'arbre de segments, ce qui garantit une complexité temporelle de \\(O(\\log n)\\).
Modification d'Intervalle (Propagation Paresseuse)
Modifier un grand intervalle de points un par un serait inefficace (\\(O(N)\\)). Pour des modifications d'intervalle, nous introduisons la technique de la propagation paresseuse (lazy propagation). L'idée est d'ajouter un marqueur paresseux (lazy tag) à un nœud pour indiquer qu'une modification a été appliquée à son intervalle, mais que cette modification n'a pas encore été propagée à ses enfants.
Lorsqu'un nœud est entièrement couvert par une opération de modification d'intervalle, nous mettons à jour sa valeur agrégée et appliquons un marqueur paresseux, sans toucher immédiatement à ses enfants. Le marqueur paresseux indique que ses enfants devront être mis à jour ultérieurement. Si une opération (modification ou requête) nécessite de descendre dans un nœud qui a un marqueur paresseux, nous "poussons" d'abord ce marqueur vers ses enfants, en mettant à jour leurs valeurs et en leur appliquant le marqueur, puis en effaçant le marqueur du parent. Cette technique réduit la complexité à \\(O(\\log n)\\) par opération, car les mises à jour ne sont effectuées que lorsque cela est strictement nécessaire.
2. Exemples d'Application
Problème 1 : Somme d'Intervalle et Ajout sur Intervalle
Ce problème classique implique de maintenir la somme des éléments sur des intervalles, et de pouvoir ajouter une valeur constante à tous les éléments d'un intervalle donné. La propagation paresseuse est essentielle ici.
#include <iostream>
#include <vector>
#include <numeric> // Pour std::iota ou pour des opérations numériques
const int MAX_N_SEGS = 100010; // Taille maximale pour le tableau d'origine
struct NoeudSegSomme {
int debut, fin;
long long somme;
long long deltaLazy; // Marqueur paresseux pour l'ajout
};
NoeudSegSomme arbreSomme[MAX_N_SEGS * 4];
std::vector<long long> tableauInitial; // Pour stocker les valeurs initiales
// Met à jour la somme du nœud parent à partir de ses enfants
void remonterSomme(int indexNoeud) {
arbreSomme[indexNoeud].somme = arbreSomme[2 * indexNoeud].somme + arbreSomme[2 * indexNoeud + 1].somme;
}
// Construit l'arbre de segments
void construireSomme(int indexNoeud, int debutIntervalle, int finIntervalle) {
arbreSomme[indexNoeud].debut = debutIntervalle;
arbreSomme[indexNoeud].fin = finIntervalle;
arbreSomme[indexNoeud].deltaLazy = 0; // Initialise le marqueur paresseux
if (debutIntervalle == finIntervalle) {
arbreSomme[indexNoeud].somme = tableauInitial[debutIntervalle-1]; // tableauInitial est 0-indexé, l'énoncé 1-indexé
return;
}
int milieu = debutIntervalle + (finIntervalle - debutIntervalle) / 2;
construireSomme(2 * indexNoeud, debutIntervalle, milieu);
construireSomme(2 * indexNoeud + 1, milieu + 1, finIntervalle);
remonterSomme(indexNoeud);
}
// Propagateur les marqueurs paresseux aux enfants
void propagerMarqueurSomme(int indexNoeud) {
if (arbreSomme[indexNoeud].deltaLazy != 0) {
// Appliquer la modification aux enfants
long long valLazy = arbreSomme[indexNoeud].deltaLazy;
// Enfant gauche
long long tailleGauche = arbreSomme[2 * indexNoeud].fin - arbreSomme[2 * indexNoeud].debut + 1;
arbreSomme[2 * indexNoeud].somme += valLazy * tailleGauche;
arbreSomme[2 * indexNoeud].deltaLazy += valLazy; // Transférer le marqueur
// Enfant droit
long long tailleDroit = arbreSomme[2 * indexNoeud + 1].fin - arbreSomme[2 * indexNoeud + 1].debut + 1;
arbreSomme[2 * indexNoeud + 1].somme += valLazy * tailleDroit;
arbreSomme[2 * indexNoeud + 1].deltaLazy += valLazy; // Transférer le marqueur
arbreSomme[indexNoeud].deltaLazy = 0; // Effacer le marqueur du nœud parent
}
}
// Modifie un intervalle [qDebut, qFin] en ajoutant 'valeur'
void modifierIntervalleSomme(int indexNoeud, int qDebut, int qFin, long long valeur) {
// Si l'intervalle du nœud est entièrement inclus dans la plage de requête
if (qDebut <= arbreSomme[indexNoeud].debut && qFin >= arbreSomme[indexNoeud].fin) {
long long tailleIntervalle = arbreSomme[indexNoeud].fin - arbreSomme[indexNoeud].debut + 1;
arbreSomme[indexNoeud].somme += valeur * tailleIntervalle;
arbreSomme[indexNoeud].deltaLazy += valeur; // Appliquer le marqueur paresseux
return;
}
propagerMarqueurSomme(indexNoeud); // Propager le marqueur avant de descendre
int milieu = arbreSomme[indexNoeud].debut + (arbreSomme[indexNoeud].fin - arbreSomme[indexNoeud].debut) / 2;
// Si la plage de modification chevauche l'enfant gauche
if (qDebut <= milieu) {
modifierIntervalleSomme(2 * indexNoeud, qDebut, qFin, valeur);
}
// Si la plage de modification chevauche l'enfant droit
if (qFin > milieu) {
modifierIntervalleSomme(2 * indexNoeud + 1, qDebut, qFin, valeur);
}
remonterSomme(indexNoeud); // Remonter les sommes après les modifications
}
// Interroge la somme sur un intervalle [qDebut, qFin]
long long interrogerSomme(int indexNoeud, int qDebut, int qFin) {
// Si l'intervalle du nœud est entièrement inclus dans la plage de requête
if (qDebut <= arbreSomme[indexNoeud].debut && qFin >= arbreSomme[indexNoeud].fin) {
return arbreSomme[indexNoeud].somme;
}
propagerMarqueurSomme(indexNoeud); // Propager le marqueur avant de descendre
long long resultat = 0;
int milieu = arbreSomme[indexNoeud].debut + (arbreSomme[indexNoeud].fin - arbreSomme[indexNoeud].debut) / 2;
if (qDebut <= milieu) {
resultat += interrogerSomme(2 * indexNoeud, qDebut, qFin);
}
if (qFin > milieu) {
resultat += interrogerSomme(2 * indexNoeud + 1, qDebut, qFin);
}
return resultat;
}
Problème 2 : Somme d'Intervalle, Multiplication et Ajout sur Intervalle (Modulo)
Ce problème est plus complexe car il combine deux marqueurs paresseux : multiplication et addition, le tout sous un module. Il est crucial de gérer l'ordre des opérations (multiplicatino avant addition) et l'impact de l'un sur l'autre lors de la propagation.
#include <iostream>
#include <vector>
#include <numeric>
const int MAX_N_SEGS_MULT = 100010;
int MOD_VAL; // Global pour le module
struct NoeudSegMultAdd {
int debut, fin;
long long somme;
long long lazyMult; // Marqueur pour la multiplication
long long lazyAdd; // Marqueur pour l'addition
};
NoeudSegMultAdd arbreMultAdd[MAX_N_SEGS_MULT * 4];
std::vector<long long> tableauInitialMultAdd;
void remonter(int indexNoeud) {
arbreMultAdd[indexNoeud].somme = (arbreMultAdd[2 * indexNoeud].somme + arbreMultAdd[2 * indexNoeud + 1].somme) % MOD_VAL;
}
void appliquerMarqueurs(int indexNoeud, long long multVal, long long addVal) {
// Calculer la taille de l'intervalle du nœud
long long tailleIntervalle = arbreMultAdd[indexNoeud].fin - arbreMultAdd[indexNoeud].debut + 1;
// Appliquer la multiplication
arbreMultAdd[indexNoeud].somme = (arbreMultAdd[indexNoeud].somme * multVal) % MOD_VAL;
arbreMultAdd[indexNoeud].lazyMult = (arbreMultAdd[indexNoeud].lazyMult * multVal) % MOD_VAL;
arbreMultAdd[indexNoeud].lazyAdd = (arbreMultAdd[indexNoeud].lazyAdd * multVal) % MOD_VAL; // L'ajout doit aussi être multiplié
// Appliquer l'addition
arbreMultAdd[indexNoeud].somme = (arbreMultAdd[indexNoeud].somme + addVal * tailleIntervalle) % MOD_VAL;
arbreMultAdd[indexNoeud].lazyAdd = (arbreMultAdd[indexNoeud].lazyAdd + addVal) % MOD_VAL;
}
void propagerMarqueurMultAdd(int indexNoeud) {
if (arbreMultAdd[indexNoeud].lazyMult == 1 && arbreMultAdd[indexNoeud].lazyAdd == 0) return; // Aucun marqueur actif
// Appliquer les marqueurs du parent aux enfants
appliquerMarqueurs(2 * indexNoeud, arbreMultAdd[indexNoeud].lazyMult, arbreMultAdd[indexNoeud].lazyAdd);
appliquerMarqueurs(2 * indexNoeud + 1, arbreMultAdd[indexNoeud].lazyMult, arbreMultAdd[indexNoeud].lazyAdd);
// Effacer les marqueurs du parent
arbreMultAdd[indexNoeud].lazyMult = 1; // Le neutre pour la multiplication
arbreMultAdd[indexNoeud].lazyAdd = 0; // Le neutre pour l'addition
}
void construireMultAdd(int indexNoeud, int debutIntervalle, int finIntervalle) {
arbreMultAdd[indexNoeud].debut = debutIntervalle;
arbreMultAdd[indexNoeud].fin = finIntervalle;
arbreMultAdd[indexNoeud].lazyMult = 1; // Initialisation par défaut (neutre pour la multiplication)
arbreMultAdd[indexNoeud].lazyAdd = 0; // Initialisation par défaut (neutre pour l'addition)
if (debutIntervalle == finIntervalle) {
arbreMultAdd[indexNoeud].somme = tableauInitialMultAdd[debutIntervalle-1] % MOD_VAL;
return;
}
int milieu = debutIntervalle + (finIntervalle - debutIntervalle) / 2;
construireMultAdd(2 * indexNoeud, debutIntervalle, milieu);
construireMultAdd(2 * indexNoeud + 1, milieu + 1, finIntervalle);
remonter(indexNoeud);
}
void modifierMult(int indexNoeud, int qDebut, int qFin, long long multVal) {
if (qDebut <= arbreMultAdd[indexNoeud].debut && qFin >= arbreMultAdd[indexNoeud].fin) {
appliquerMarqueurs(indexNoeud, multVal, 0); // Appliquer uniquement la multiplication
return;
}
propagerMarqueurMultAdd(indexNoeud);
int milieu = arbreMultAdd[indexNoeud].debut + (arbreMultAdd[indexNoeud].fin - arbreMultAdd[indexNoeud].debut) / 2;
if (qDebut <= milieu) modifierMult(2 * indexNoeud, qDebut, qFin, multVal);
if (qFin > milieu) modifierMult(2 * indexNoeud + 1, qDebut, qFin, multVal);
remonter(indexNoeud);
}
void modifierAdd(int indexNoeud, int qDebut, int qFin, long long addVal) {
if (qDebut <= arbreMultAdd[indexNoeud].debut && qFin >= arbreMultAdd[indexNoeud].fin) {
appliquerMarqueurs(indexNoeud, 1, addVal); // Appliquer uniquement l'addition
return;
}
propagerMarqueurMultAdd(indexNoeud);
int milieu = arbreMultAdd[indexNoeud].debut + (arbreMultAdd[indexNoeud].fin - arbreMultAdd[indexNoeud].debut) / 2;
if (qDebut <= milieu) modifierAdd(2 * indexNoeud, qDebut, qFin, addVal);
if (qFin > milieu) modifierAdd(2 * indexNoeud + 1, qDebut, qFin, addVal);
remonter(indexNoeud);
}
long long interrogerMultAdd(int indexNoeud, int qDebut, int qFin) {
if (qDebut <= arbreMultAdd[indexNoeud].debut && qFin >= arbreMultAdd[indexNoeud].fin) {
return arbreMultAdd[indexNoeud].somme;
}
propagerMarqueurMultAdd(indexNoeud);
long long resultat = 0;
int milieu = arbreMultAdd[indexNoeud].debut + (arbreMultAdd[indexNoeud].fin - arbreMultAdd[indexNoeud].debut) / 2;
if (qDebut <= milieu) resultat = (resultat + interrogerMultAdd(2 * indexNoeud, qDebut, qFin)) % MOD_VAL;
if (qFin > milieu) resultat = (resultat + interrogerMultAdd(2 * indexNoeud + 1, qDebut, qFin)) % MOD_VAL;
return resultat;
}
Problème 3 : Maximum d'Intervalle, Remplacement d'Intervalle, Ajout sur Intervalle
Ce problème introduit un marqueur de "couverture" ou de "remplacement" (set value) qui a priorité sur l'ajout. Si un intervalle est "couvert" par une nouvelle valeur, toute opération d'ajout précédente sur cet intervalle devient obsolète.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::max
const int MAX_N_FUSU = 1000010;
const long long INF_NEG = -4e18; // Représente -inf pour les maxima
struct NoeudSegFusu {
int debut, fin;
long long maximum;
long long lazyAdd;
long long lazySet; // Marqueur pour le remplacement (couverture)
};
NoeudSegFusu arbreFusu[MAX_N_FUSU * 4];
std::vector<long long> tableauInitialFusu;
void remonterFusu(int indexNoeud) {
arbreFusu[indexNoeud].maximum = std::max(arbreFusu[2 * indexNoeud].maximum, arbreFusu[2 * indexNoeud + 1].maximum);
}
void appliquerMarqueurFusu(int indexNoeud, long long setVal, long long addVal) {
// Si un marqueur de remplacement est présent
if (setVal != INF_NEG) { // Remplacement
arbreFusu[indexNoeud].maximum = setVal;
arbreFusu[indexNoeud].lazyAdd = 0; // Réinitialiser l'ajout car la valeur est remplacée
arbreFusu[indexNoeud].lazySet = setVal;
}
// Si un marqueur d'ajout est présent
if (addVal != 0) { // Addition
arbreFusu[indexNoeud].maximum += addVal;
arbreFusu[indexNoeud].lazyAdd += addVal;
}
}
void propagerMarqueurFusu(int indexNoeud) {
if (arbreFusu[indexNoeud].lazySet == INF_NEG && arbreFusu[indexNoeud].lazyAdd == 0) return; // Aucun marqueur actif
// Propagation aux enfants
// D'abord le marqueur de remplacement (s'il existe)
if (arbreFusu[indexNoeud].lazySet != INF_NEG) {
arbreFusu[2 * indexNoeud].lazySet = arbreFusu[indexNoeud].lazySet;
arbreFusu[2 * indexNoeud + 1].lazySet = arbreFusu[indexNoeud].lazySet;
arbreFusu[2 * indexNoeud].maximum = arbreFusu[indexNoeud].lazySet;
arbreFusu[2 * indexNoeud + 1].maximum = arbreFusu[indexNoeud].lazySet;
arbreFusu[2 * indexNoeud].lazyAdd = 0; // L'ajout est effacé par le remplacement
arbreFusu[2 * indexNoeud + 1].lazyAdd = 0;
}
// Ensuite le marqueur d'ajout
if (arbreFusu[indexNoeud].lazyAdd != 0) {
arbreFusu[2 * indexNoeud].maximum += arbreFusu[indexNoeud].lazyAdd;
arbreFusu[2 * indexNoeud + 1].maximum += arbreFusu[indexNoeud].lazyAdd;
arbreFusu[2 * indexNoeud].lazyAdd += arbreFusu[indexNoeud].lazyAdd;
arbreFusu[2 * indexNoeud + 1].lazyAdd += arbreFusu[indexNoeud].lazyAdd;
}
// Effacer les marqueurs du parent
arbreFusu[indexNoeud].lazySet = INF_NEG;
arbreFusu[indexNoeud].lazyAdd = 0;
}
void construireFusu(int indexNoeud, int debutIntervalle, int finIntervalle) {
arbreFusu[indexNoeud].debut = debutIntervalle;
arbreFusu[indexNoeud].fin = finIntervalle;
arbreFusu[indexNoeud].lazyAdd = 0;
arbreFusu[indexNoeud].lazySet = INF_NEG; // -inf indique aucun remplacement en attente
if (debutIntervalle == finIntervalle) {
arbreFusu[indexNoeud].maximum = tableauInitialFusu[debutIntervalle-1];
return;
}
int milieu = debutIntervalle + (finIntervalle - debutIntervalle) / 2;
construireFusu(2 * indexNoeud, debutIntervalle, milieu);
construireFusu(2 * indexNoeud + 1, milieu + 1, finIntervalle);
remonterFusu(indexNoeud);
}
void modifierSet(int indexNoeud, int qDebut, int qFin, long long setVal) {
if (qDebut <= arbreFusu[indexNoeud].debut && qFin >= arbreFusu[indexNoeud].fin) {
appliquerMarqueurFusu(indexNoeud, setVal, 0); // Appliquer remplacement
return;
}
propagerMarqueurFusu(indexNoeud);
int milieu = arbreFusu[indexNoeud].debut + (arbreFusu[indexNoeud].fin - arbreFusu[indexNoeud].debut) / 2;
if (qDebut <= milieu) modifierSet(2 * indexNoeud, qDebut, qFin, setVal);
if (qFin > milieu) modifierSet(2 * indexNoeud + 1, qDebut, qFin, setVal);
remonterFusu(indexNoeud);
}
void modifierAddFusu(int indexNoeud, int qDebut, int qFin, long long addVal) {
if (qDebut <= arbreFusu[indexNoeud].debut && qFin >= arbreFusu[indexNoeud].fin) {
appliquerMarqueurFusu(indexNoeud, INF_NEG, addVal); // Appliquer addition (pas de remplacement)
return;
}
propagerMarqueurFusu(indexNoeud);
int milieu = arbreFusu[indexNoeud].debut + (arbreFusu[indexNoeud].fin - arbreFusu[indexNoeud].debut) / 2;
if (qDebut <= milieu) modifierAddFusu(2 * indexNoeud, qDebut, qFin, addVal);
if (qFin > milieu) modifierAddFusu(2 * indexNoeud + 1, qDebut, qFin, addVal);
remonterFusu(indexNoeud);
}
long long interrogerMaxFusu(int indexNoeud, int qDebut, int qFin) {
if (qDebut <= arbreFusu[indexNoeud].debut && qFin >= arbreFusu[indexNoeud].fin) {
return arbreFusu[indexNoeud].maximum;
}
propagerMarqueurFusu(indexNoeud);
long long resultat = INF_NEG;
int milieu = arbreFusu[indexNoeud].debut + (arbreFusu[indexNoeud].fin - arbreFusu[indexNoeud].debut) / 2;
if (qDebut <= milieu) resultat = std::max(resultat, interrogerMaxFusu(2 * indexNoeud, qDebut, qFin));
if (qFin > milieu) resultat = std::max(resultat, interrogerMaxFusu(2 * indexNoeud + 1, qDebut, qFin));
return resultat;
}
Problème 4 : Variance d'Intervalle
Pour calculer la variance d'un intervalle, on utilise la formule \\(s^2 = \frac{\sum x_i^2}{n} - \bar{x}^2\\), où \\(\bar{x}\\) est la moyenne de l'intervalle. Pour gérer des mises à jour d'ajout sur intervalle et des requêtes de variance, l'arbre de segments doit maintenir deux informations pour chaque nœud : la somme des éléments (\\(\sum x_i\\)) et la somme des carrés des éléments (\\(\sum x_i^2\\)).
Lors d'une opération d'ajout d'une valeur \\(K\\) à un intervalle \\(\[L, R\]\\) :
- La nouvelle somme \\(\sum x'_i\\) devient \\(\sum x_i + K \times \text{longueur de l'intervalle}\\).
- La nouvelle somme des carrés \\(\sum (x'_i)^2\\) est \\(\sum (x_i + K)^2 = \sum (x_i^2 + 2Kx_i + K^2) = \sum x_i^2 + 2K \sum x_i + K^2 \times \text{longueur de l'intervalle}\\).
En maintenant ces deux sommes et en utilisant la propagation paresseuse, il est possible de calculer la variance en \\(O(\\log n)\\).
Problème 5 : Somme Maximale de Sous-tableau Contigu
Ce problème requiert une approche plus sophistiquée dans la fonction de fusion des enfants. Pour un nœud parenet, la somme maximale de sous-tableau contigu peut se trouver entièrement dans son enfant gauche, entièrement dans son enfant droit, ou chevaucher la frontière entre les deux enfants. Pour gérer ce dernier cas, chaque nœud doit stocker quatre valeurs :
somme_totale: la somme de tous les éléments de l'intervalle du nœud.max_prefix_sum: la somme maximale d'un préfixe de l'intervalle du nœud.max_suffix_sum: la somme maximale d'un suffixe de l'intervalle du nœud.max_subarray_sum: la somme maximale d'un sous-tableau contigu de l'intervalle du nœud.
La fusion de ces valeurs pour un parent à partir de ses enfants nécessite des règles spécifiques pour chaque attribut. Par exemple, max_subarray_sum(parent) sera le maximum entre max_subarray_sum(gauche), max_subarray_sum(droit) et max_suffix_sum(gauche) + max_prefix_sum(droit).
Problème 6 : Opérations sur Séquences (Remplacement, Inversion, Somme, Max Sous-tableau de 1s)
Ce type de problème combine des opérations complexes sur les intervalles. Il nécessite souvent plusieurs marqueurs paresseux (par exemple, un pour le remplacement, un pour l'inversion des bits 0/1). L'ordre d'application de ces marqueurs est crucial. De plus, la "somme maximale de sous-tableau de 1s" est une variante du problème de somme maximale de sous-tableau contigu, adaptée aux séquences binaires.
Problème 7 : Somme de Sinus et Cosinus sur Intervalle avec Ajout
Lorsqu'on ajoute une constante \\(d\\) à tous les éléments \\(a_i\\) d'un intervalle, on cherche à calculer \\(\sum \sin(a_i + d)\\) et \\(\sum \cos(a_i + d)\\). En utilisant les formules d'addition trigonométriques :
- \\(\sin(\alpha + \theta) = \sin\alpha\cos\theta + \cos\alpha\sin\theta\\)
- \\(\cos(\alpha + \theta) = \cos\alpha\cos\theta - \sin\alpha\sin\theta\\)
On peut observer que :
\\[ \sum_{i=1}^n \sin(a_i + d) = \cos d \cdot \left(\sum_{i=1}^n \sin a_i\right) + \sin d \cdot \left(\sum_{i=1}^n \cos a_i\right) \\]
Ainsi, pour gérer cette opération, un nœud de l'arbre de segments doit maintenir la somme des sinus (\\(\sum \sin a_i\\)) et la somme des cosinus (\\(\sum \cos a_i\\)) de son intervalle. La propagation paresseuse appliquerait les transformations selon les formules ci-dessus en fonction du \\(d\\) à ajouter.