Estrutura de dados dinâmicos que verifica todas as somas do prefixo de uma subsequência são>= 0 e soma é= 0

Question

permite considerar sequências cujos elementos são $ - 1,0,1 $ .


Subsequência $ a [i ... j] $ é $ bom $ se soma de seus elementos $= 0 $ .


Exemplo: para sequência $ 1,1,0, -1, -1,1 $ subsequência $ 1,0, -1, -1,1 $ é $ Bom $ .

. Subsequência $ a [i ... j] $ é $ supergood $ se é bom e cada O prefixo é $>= 0 $
Exemplo: para sequência $ 1,1,0, -1, -1,1 $ subsequência $ 1,0, -1, -1,1 $ não é $ supergood $ mas $ 1,0, -1 $ é $ supergood $ .

Agora eu quero ter estrutura dinâmica de dados que me permite eficazmente essas operações:

• inserção (s, x, i) - insere $ x $ em $ s $ em < Classe Span="Recipiente de Matemática"> $ i $ 'Th posição
• remove (s, i) - remova $ i $ 'th elemento
• issupergood (s, i, j) - verifica se subsequência $ i $ , $ J $ é supergood

A solução pode ser árvore AVL com soma de elementos na subárvore esquerda e direita. É fácil de atualizar e nos permite verificar se a subsequência é boa em $ o (\ log (n)) $ :

.
1. encontrar nó i (dizer v) $ \ o (\ log (n)) $
2. encontrar nó j (let você) $ \ o (\ log (n)) $
3. verificar se v.val + v.lsum - u.lsum== 0 $ \ o (1) $

Mas se trata de verificar a condição supergood, não vejo como.

Answer 1

Aumentar a árvore para armazenar, para cada subárvore, o mínimo do prefixo soma da sequência de elementos nessa subárvore. Então você pode verificar a condição supergood em $ o (\ log n) $ tempo. É o seu exercício, então eu vou deixar você descobrir os detalhes.

Dica # 1: Cada prefixo pode ser decomposto em uma união de $ o (\ log n) $ subtrees.

Dica # 2: o mínimo da soma do prefixo de elementos $ [x_1, \ pontos, x_k] $ é menor de (a) o mínimo de O prefixo-soma de elementos $ [x_1, \ pontos, x_j] $ , (b), a soma de elementos $ [x_1, \ Dots, x_j] $ mais o mínimo de suma prefixo de elementos $ [x_ {j + 1}, \ pontos, x_k] $ . Agora, deixe $ [x_1, \ pontos, x_j] $ denotam os elementos na subárvore esquerda de um nó e $ [ x_ {j + 1}, \ Dots, x_k] $ o elemento no nó e os elementos na subárvore direita, e isso fornece uma maneira de recolocar os valores aumentados em um nó dado os valores aumentados em sua duas crianças.

---

Em geral, a estratégia típica com o aumento é que você deseja escolher valores aumentados para que (1) você possa atualizar ou recolocar os valores aumentados em um nó eficientemente (tipicamente, em $ O (1) $ tempo), dados os valores aumentados em seus dois filhos, e (2) você pode responder uma consulta eficientemente (tipicamente, em $ O (\ log n) $ tempo), usando os valores aumentados. Muitas vezes nós lidamos (2) aproveitando o fato de que todo intervalo de valores consecutivos pode ser decomposto em uma união disjunta de $ O (\ log n) $ subestres.