Árvore de segmentos estática

AS(S): cria uma árvore de segmentos para o conjunto S de intervalos
Segments(r,x): devolve uma lista com os segmentos na AS r que contém x
Print(r): imprime a AS r, com a lista de segmentos para cada nó

Codificação das operações:

1 <x> significa Segments(x)
2     significa Print()

A primeira linha contém o número n de segmentos na coleção.
As n linhas seguintes contêm pares (s,f), com os extremos de cada segmento da coleção.
Depois disso, seguem as instruções conforme a codificação acima.

10
1 8
2 4
3 9
3 11
9 12
4 10
6 11
11 13
14 14
16 17
2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17

A ordem em que aparecem os segmentos na lista é irrelevante.

Na impressão da árvore, imprimimos o intervalo referente ao nó, e a lista dos identificadores dos segmentos deste nó.

               (-inf,1)
            (-inf,1]
               [1,1] 1
         (-inf,2]
               (1,2)
            (1,2] 1
               [2,2] 2
      (-inf,4]
               (2,3)
            (2,3]
               [3,3] 3 4
         (2,4] 1 2
               (3,4)
            (3,4] 3 4
               [4,4] 6
   (-inf,10]
               (4,6)
            (4,6]
               [6,6] 7
         (4,8] 1 3
               (6,8)
            (6,8] 7
               [8,8]
      (4,10] 4 6
               (8,9)
            (8,9] 3
               [9,9] 5
         (8,10] 7
               (9,10)
            (9,10] 5
               [10,10]
(-inf,+inf)
               (10,11)
            (10,11] 4 7
               [11,11] 8
         (10,12] 5
               (11,12)
            (11,12] 8
               [12,12]
      (10,14]
               (12,13)
            (12,13] 8
               [13,13]
         (12,14]
               (13,14)
            (13,14]
               [14,14] 9
   (10,+inf)
               (14,16)
            (14,16]
               [16,16] 10
         (14,17)
            (16,17) 10
      (14,+inf)
            [17,17] 10
         [17,+inf)
            (17,+inf)
1
1 2
1 2 3 4
1 2 3 4 6
1 3 4 6
1 3 4 6 7
1 3 4 6 7
1 3 4 6 7
3 4 5 6 7
4 5 6 7
4 5 7 8
5 8
8
9
nenhum segmento
10
10

Árvore de segmentos dinâmica

ASD(): cria e devolve uma AS dinâmica vazia
Segments(r,x): devolve uma lista com os segmentos na AS dinâmica r que contém x
Insert(r,s,f): insere na AS dinâmica r o intervalo [s,f]
PrintASD(r): aciona o Print para cada AS da ASD r

Seu programa deve começar com uma ASD vazia.

Codificação das operações:

1 <s> <f> significa Insert(s,f)
2 <x>     significa Segments(x)
3         significa PrintADS()

1 1 8
1 2 4
1 3 9
1 3 11
1 9 12
1 4 10
2 7
2 11
1 6 11
2 7
2 11
2 13
2 0
1 11 13
1 14 14
1 16 17
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17

A ordem em que aparecem os segmentos na lista é irrelevante.

1 3 4 6
4 5
1 3 4 6 7
4 5 7
nenhum segmento
nenhum segmento
1
1 2
1 2 3 4
1 2 3 4 6
1 3 4 6
1 3 4 6 7
1 3 4 6 7
1 3 4 6 7
3 4 5 6 7
4 5 6 7
4 5 7 8
5 8
8
9
nenhum segmento
10
10