Propagation paresseuse pour les mises à jour de plages
Différer les mises à jour sur des plages entières
Propagation paresseuse pour les mises à jour de plages est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Le problème des mises à jour d'intervalles
Que faire si une requête demande d'ajouter 5 à chaque élément de l à r ? Toucher chaque feuille coûte O(n) par mise à jour, ce qui est bien trop lent pour de nombreuses mises à jour d'intervalles. 😰
L'idée de la propagation différée
La propagation différée permet à un nœud de mémoriser une modification en attente sans la transmettre immédiatement à ses enfants. Le travail est reporté jusqu'à ce que vous ayez réellement besoin de ces enfants.
Un second tableau pour le travail en attente
En plus de l'arbre, nous conservons un tableau des reports. lazy[node] contient une mise à jour qui s'applique à tout l'intervalle du nœud, mais qui n'a pas encore été propagée vers le bas.
lazy = [0] * (4 * n)Appliquer à un nœud entier
Lorsqu'une mise à jour couvre entièrement un nœud, ajustez sa valeur stockée et empilez la modification dans lazy, puis arrêtez-vous. Il n'est pas nécessaire de descendre dans l'arbre.
seg[node] += (r - l + 1) * val
lazy[node] += valPropager vers le bas avant de descendre
Avant de visiter les enfants, propagez vers le bas toute valeur différée en attente vers chacun d'eux. Les enfants restent ainsi corrects exactement au moment où vous les lisez.
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0Trois cas par nœud
À chaque nœud, l'intervalle de requête est disjoint, le couvre entièrement ou le recouvre partiellement. Ignorez, appliquez avec propagation différée ou explorez récursivement les deux moitiés, respectivement.
Les mises à jour différées restent logarithmiques
Une mise à jour d'intervalle ne touche que O(log n) nœuds, car les nœuds entièrement couverts s'arrêtent tôt. C'est tout le bénéfice de la propagation différée. ⚡
Propager aussi les requêtes vers le bas
Les requêtes d’intervalle doivent elles aussi être propagées vers le bas avant la récursion, afin de lire les valeurs actualisées des enfants. Oublier cette étape est l’erreur classique de la propagation différée.
Remonter après la récursion
Après avoir mis à jour les enfants, recombinez le parent à partir de leurs valeurs. Cette remontée garantit la cohérence de chaque nœud interne avec son sous-arbre.
seg[node] = seg[2*node] + seg[2*node+1]Affectation ou addition
La propagation différée fonctionne avec de nombreuses opérations, mais l’affectation et l’addition se combinent différemment. Déterminez comment fusionner deux mises à jour en attente avant de coder.
Quand la propagation différée vaut le coup
N’utilisez la propagation différée que lorsque vous avez réellement besoin de mises à jour d’intervalle. Pour les seules mises à jour ponctuelles, un arbre de segments classique est plus simple et suffisant.
Vérification rapide
Que faut-il faire avant de descendre récursivement dans les enfants d’un nœud ?
Récapitulatif : mises à jour différées
Vous avez appris la propagation différée : stocker les changements en attente, les propager vers le bas avant de descendre, remonter après la mise à jour, et obtenir des mises à jour d’intervalle en O(log n). 🎉
Questions Fréquemment Posées
La leçon « Propagation paresseuse pour les mises à jour de plages » est-elle gratuite ?
Oui — le texte complet de « Propagation paresseuse pour les mises à jour de plages » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Propagation paresseuse pour les mises à jour de plages » ?
Différer les mises à jour sur des plages entières Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Propagation paresseuse pour les mises à jour de plages » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Arbre de Fenwick pour les sommes préfixes
- Inversions avec un BIT
- Arbre de segments : construction et requêtes
- Propagation paresseuse pour les mises à jour de plages