Struttura dei dati dinamici che controlla tutte le somme di prefisso di una successiva>= 0 e somma è= 0

Question

consente di considerare sequenze i cui elementi sono $ - 1,0,1 $ .
. Successive $ a [i ... j] $ è $ buono $ se somma dei suoi elementi < class="container math"> $= 0 $ .
. Esempio: per sequenza $ 1,1,0, -1, -1,1 $ successive $ 1,0, -1, -1,1 $ è $ Buono $ .

Successive $ a [i ... j] $ è $ superdood $ Se è buono e ogni suo prefisso-somma è $>= 0 $
Esempio: per sequenza $ 1,1,0, -1, -1,1 $ successive $ 1,0, -1, -1,1 $ non è $ supergood $ ma $ 1,0, -1 $ $ supergood $ .

Ora voglio avere una struttura dati dinamica che mi consente di fare in modo efficiente queste operazioni:

.
• insert (s, x, i) - inserisce $ x $ in $ s $ su < Span Class="Math-Container"> $ I $ 'TH POSIZIONE
• rimuovi (i) - rimuovi $ i $ 'l' elemento
• ISUPERGOOOOOD (I, I, J) - controlla se la successiva $ i $ , $ j $ è supergood

La soluzione potrebbe essere l'albero AVL con la somma di elementi nel sottosuolo sinistro e destro. È facile per l'aggiornamento e ci consente di verificare se la successiva è buona in $ o (\ log (n)) $ :

.
1. Trova nodo I (Let Dy V) $ \ o (\ log (n)) $
2. Trova nodo j (lascia dire u) $ \ o (\ log (n)) $
3. Controllare se v.val + v.lsum - u.lsum== 0 $ \ o (1) $

Ma se si tratta di controllare la condizione SuperGood, non vedo come.

Answer 1

Aumentare l'albero da archiviare, per ogni sottostruttura, il minimo delle somme prefisso della sequenza di elementi in quella sottosmellata. Quindi è possibile controllare la condizione SuperGood in $ o (\ log n) $ tempo. È il tuo esercizio, quindi ti permetterò di elaborare i dettagli.

Suggerimento n. 1: ogni prefisso può essere decomposto in un'unione di $ o (\ log n) $ substrees.

Suggerimento n. 2: il minimo della somma prefisso degli elementi $ [x_1, \ dots, x_k] $ è il più piccolo di (A) il minimo di La somma prefissa degli elementi $ [x_1, \ dots, x_j] $ , (b), la somma degli elementi $ [x_1, \ dots, x_j] $ più il minimo di prefisso-somma di elementi $ [x_ {j + 1}, \ dots, x_k] $ . Ora Let $ [x_1, \ dots, x_j] $ Dennare gli elementi nel sottosuolo sinistro di un nodo e $ [ X_ {J + 1}, \ Dots, X_K] $ L'elemento nel nodo e gli elementi nel sottosuolo destro e questo ti dà un modo per ricomputare i valori aumentati in un nodo dato i valori aumentati nel suo Due bambini.

---

.

In generale, la strategia tipica con l'aumento è che si desidera scegliere valori aumentati in modo che (1) è possibile aggiornare o ricomputare i valori aumentati in un nodo in modo efficiente (in genere, in $ O (1) $ tempo), dato i valori aumentati nei suoi due figli, e (2) è possibile rispondere a una query in modo efficiente (in genere, in $ o (\ log n) $ tempo), utilizzando i valori aumentati. Spesso gestiremo (2) sfruttando il fatto che ogni intervallo di valori consecutivi può essere decomposto in un'unione disgiunta di $ o (\ log n) $ substrees.