Introduction à l'Arbre Cartésien
L'arbre cartésien est une structure de données arborescente binaire dérivée d'une séquence de nombres. Il est particulièrement utile pour résoudre des problèmes tels que les requêtes de minimum/maximum sur un intervalle (RMQ) et les requêtes de type "top-k". Introduit par Jean Vuillemin en 1980 pour résoudre des problèmes de recherche géométrique, il combine de manière élégante les propriétés d'un arbre binaire de recherche et d'un tas (heap).
Propriétés Structurelles
Bien qu'il s'agisse d'une structure arborescente, l'arbre cartésien représente essentiellement une transformation d'une séquence linéaire. Chaque nœud de l'arbre possède deux attributs principaux : son index dans la séquence originale et sa valeur.
- Propriété de l'arbre binaire de recherche (BST) : Les index des nœuds respectent l'ordre de la séquence originale. Un parcours infixe (in-order) de l'arbre restitue exactement la séquence d'origine. Pour tout nœud $x$, on a $index(gauche) < index(x) < index(droite)$.
- Propriété du tas (Heap) : La valeur d'un nœud parent est toujours inférieure (ou supérieure, selon qu'il s'agit d'un tas min ou max) aux valeurs de ses enfants. Pour un tas min, $valeur(x) \le valeur(gauche)$ et $valeur(x) \le valeur(droite)$.
Construction en Temps Linéaire
La construction naive d'un arbre cartésien prendrait $O(n^2)$ dans le pire des cas. Cependant, il est possible de construire l'arbre en temps linéaire $O(n)$ en utilisant une pile monotone pour maintenir la chaîne la plus à droite de l'arbre.
L'algorithme de construction est le suivant :
- Parcourir la séquence de gauche à droite.
- Pour chaque élément, dépiler les éléments de la pile dont la valeur est supérieure à l'élément courant (pour un tas min).
- Le dernier élément dépilé devient le fils gauche du nœud courant.
- Le nœud courant devient le fils droit de l'élément restant au sommet de la pile (s'il y en a un).
- Empiler le nœud courant.
Implémentation de la Construction
Voici une implémenattion moderne en C++ pour construire l'arbre et calculer des métriques de base sur les sous-arbres :
#include <iostream>
#include <vector>
#include <stack>
struct CartesianNode {
int left_child = 0;
int right_child = 0;
};
int buildCartesianTree(const std::vector<int>& values, std::vector<CartesianNode>& tree) {
int n = values.size() - 1;
std::stack<int> mono_stack;
int root = 0;
for (int i = 1; i <= n; ++i) {
int last_popped = 0;
while (!mono_stack.empty() && values[mono_stack.top()] > values[i]) {
last_popped = mono_stack.top();
mono_stack.pop();
}
if (last_popped != 0) {
tree[i].left_child = last_popped;
}
if (!mono_stack.empty()) {
tree[mono_stack.top()].right_child = i;
} else {
root = i;
}
mono_stack.push(i);
}
return root;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
if (!(std::cin >> n)) return 0;
std::vector<int> arr(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> arr[i];
}
std::vector<CartesianNode> nodes(n + 1);
buildCartesianTree(arr, nodes);
long long xor_left = 0, xor_right = 0;
for (int i = 1; i <= n; ++i) {
xor_left ^= 1LL * i * (nodes[i].left_child + 1);
xor_right ^= 1LL * i * (nodes[i].right_child + 1);
}
std::cout << xor_left << " " << xor_right << "\n";
return 0;
}
Application Avancée : Diviser pour Régner
L'arbre cartésien excelle dans les problèmes de comptage par intervalles où le maximum (ou minimum) local joue un rôle central. En utilisant une approche de type "diviser pour régner" sur l'arbre cartésien, on peut traiter efficacement des contraintes complexes, comme trouver le nombre de paires $(i, j)$ satisfaisant $a_i \times a_j \le \max(a_l \dots a_r)$.
L'idée fondamentale est de traiter la contribution de chaque sous-arbre. Pour un nœud racine représentant le maximum de l'intervalle $[l, r]$, on parcourt le plus petit des deux sous-arbres (gauche ou droit) et on utilise une structure de données comme un arbre de Fenwick (Binary Indexed Tree) pour compter les paires valides avec l'autre sous-arbre. Cette technique, souvent appelée "启发式分治" (diviser pour régner heuristique), garantit une complexité temporelle de $O(n \log^2 n)$.
Implémentation avec Arbre de Fenwick
L'exemple suivant illustre cette technique en combinant l'arbre cartésien (tas max) avec un arbre de Fenwick pour le comptage :
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
struct TreeNode {
int left = 0, right = 0;
};
class FenwickTree {
private:
std::vector<int> bit;
int n;
public:
FenwickTree(int size) : n(size), bit(size + 1, 0) {}
void add(int idx, int val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
int sum(int idx) {
int s = 0;
for (; idx > 0; idx -= idx & -idx) s += bit[idx];
return s;
}
};
int root_node;
std::vector<TreeNode> tree;
std::vector<int> orig_a;
std::vector<int> comp_a;
long long result = 0;
FenwickTree* fenwick;
std::vector<int> sorted_unique;
void construct(const std::vector<int>& vals) {
int n = vals.size() - 1;
std::stack<int> st;
for (int i = 1; i <= n; ++i) {
int last = 0;
while (!st.empty() && vals[st.top()] < vals[i]) {
last = st.top();
st.pop();
}
if (last) tree[i].left = last;
if (!st.empty()) tree[st.top()].right = i;
else root_node = i;
st.push(i);
}
}
void divide_and_conquer(int u, int l, int r) {
if (u == 0) return;
int lc = tree[u].left;
int rc = tree[u].right;
if (u - l < r - u) {
for (int i = l; i <= u; ++i) {
int limit = orig_a[u] / orig_a[i];
int pos = std::upper_bound(sorted_unique.begin() + 1, sorted_unique.end(), limit) - sorted_unique.begin() - 1;
if (pos > 0) result -= fenwick->sum(pos);
}
divide_and_conquer(rc, u + 1, r);
fenwick->add(comp_a[u], 1);
for (int i = l; i <= u; ++i) {
int limit = orig_a[u] / orig_a[i];
int pos = std::upper_bound(sorted_unique.begin() + 1, sorted_unique.end(), limit) - sorted_unique.begin() - 1;
if (pos > 0) result += fenwick->sum(pos);
}
divide_and_conquer(lc, l, u - 1);
} else {
for (int i = u; i <= r; ++i) {
int limit = orig_a[u] / orig_a[i];
int pos = std::upper_bound(sorted_unique.begin() + 1, sorted_unique.end(), limit) - sorted_unique.begin() - 1;
if (pos > 0) result -= fenwick->sum(pos);
}
divide_and_conquer(lc, l, u - 1);
fenwick->add(comp_a[u], 1);
for (int i = u; i <= r; ++i) {
int limit = orig_a[u] / orig_a[i];
int pos = std::upper_bound(sorted_unique.begin() + 1, sorted_unique.end(), limit) - sorted_unique.begin() - 1;
if (pos > 0) result += fenwick->sum(pos);
}
divide_and_conquer(rc, u + 1, r);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
if (!(std::cin >> n)) return 0;
orig_a.resize(n + 1);
sorted_unique.resize(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> orig_a[i];
sorted_unique[i] = orig_a[i];
}
std::sort(sorted_unique.begin() + 1, sorted_unique.end());
sorted_unique.erase(std::unique(sorted_unique.begin() + 1, sorted_unique.end()), sorted_unique.end());
int m = sorted_unique.size() - 1;
comp_a.resize(n + 1);
for (int i = 1; i <= n; ++i) {
comp_a[i] = std::lower_bound(sorted_unique.begin() + 1, sorted_unique.end(), orig_a[i]) - sorted_unique.begin();
}
tree.resize(n + 1);
construct(orig_a);
fenwick = new FenwickTree(m);
divide_and_conquer(root_node, 1, n);
std::cout << result << "\n";
delete fenwick;
return 0;
}