Estruturas de dados

tags: conteudo ps2020 estruturasdedados BIT segmenttree

Estruturas de dados

Estrutura de dados é o ramo da computação que estuda os diversos mecanismos de organização de dados para atender aos diferentes requisitos de processamento.

Exemplos:

Pilha, Fila, Lista encadeada, Árvores binárias, Heap, DSU
BIT, Segment tree, Treap, Sparse table

BIT (Binary Indexed Tree)

• BIT sempre tem a operação soma

Bit menos significativo

1: 001
     ^
2: 010
    ^
3: 011
     ^
4: 100
   ^
5: 101
     ^
6: 110
    ^

1: 001 -> LSB: 01
2: 010 -> LSB: 10
    ^
4: 100 -> 

5: 101 -> LSB: 001
5 + 1 = 6
6: 110 -> LSB: 010 -> 2
6 + 2 = 8
8: 1000 -> LSB = 8
16:

9: 1001 -> LSB = 1
9 + 1 = 10
10: 1010 -> LSB = 2
10 + 2 = 12
12: 1100 -> LSB = 4
12 + 4 = 16
16:

int v = x & -x

5:  001001
    000110 + 1
   
-5: 110111
 +  ^ -> signal
 5: 001001
    ______
    000000

-5: 110111
 &
 5: 001001
__________
    000001
    
 12: 01100
-12: 10011 + 00001 = 10100

 12: 01100
 &
-12: 10100
__________
     00100

int bit[N], v[N];

void add(int p, int v) {
  //vetor: v[p] += v; -> O(1)
  for(p += 2; p < N; p += p&-p) bit[p] += v; //O(log(n));
}

int query(int p) {
  int ans = 0;
  //vetor: for(int i = 1; i <= p; i++) ans += v[i]; -> O(n);
  for(p += 2; p > 0; p -= p&-p) ans += bit[p]; //O(log(n));
  return ans;
}

Obter soma até determinada posição

14: 01110 -> 14, 13
   -00010
12: 01100 -> 12, 11, 10, 9
   -00100
 8: 01000 -> 8, 7, 6, 5, 4, 3, 2, 1

• Adicionar em um ponto e consultar em range (point update/range query)

• Adicinar em range e consultar um ponto (point query/range update)
  (Ideia da soma de prefixos)
  Somar x no intervalo de l até r:
  add(l, x);
  add(r+1, -x);
  Consultar valor na posição p:
  query§;

Segment Tree

• point update/range query
• range update/point query
• range update/range query

Operações

• soma
• maximo
• minimo
• etc

pai -> filho1: 2*pai
filho2: 2*pai +1

1 -> 2 -> 4 -> 8
-> 9
-> 5 -> 10
-> 11
3 -> 6
-> 7

v = {1, 3, 2, 10, 7, 8}

1 [1, 6] (10) -> 2: [1, 3] (3) -> 4: [1, 2] (3) -> 8: [1] (1)
                                                -> 9: [2] (3)
                                  5: [3]    (2)
                 3: [4, 6] (10)-> 6: [4, 5] (10)-> 12: [4] (10)
                                                   13: [5] (7)
                                  7: [6]    (8)
                                 

atualização: soma v no intervalo de i até j
consulta: qual o máximo valor no intervalo de i a j
segment tree maximo

int st[4*N];
int lz[4*N];

  void build(int p, int l, int r) {//O(n)
    if(l == r) {st[p] = v[l]; return;}
    
    int mid = (l+r)/2;
    build(2*p, l, mid);
    build(2*p+1, mid+1, r);
    
    st[p] = max(st[2*p], st[2*p+1]);
  }
  
  int push(int p, int l, int r) {//O(1);
    if(lz[p]) {
      st[p] += lz[p];
      //st[p] += (r-l+1)*lz[p]; (segment tree de soma)
      if(l != r) {
        lz[2*p] += lz[p];
        lz[2*p+1] += lz[p];
      }
      lz[p] = 0;
    }
  }

  int query(int p, int l, int r, int i, int j) {//O(log(n))
    push(p, l, r);
    if(r < i or l > j) -INF;
    if(l >= i and r <= j) {return st[p];}
    
    int mid = (l+r)/2;
    
    return max(query(2*p, l, mid, i, j),
               query(2*p+1, mid+1, r, i, j));
  

  //point update (vamos falar de range update depois)
  void update(int p, int l, int r, int i, int j, int v) {//O(log(n))
    push(p, l, r);
    if(r < i or l > j) return;
    if(l >= i and r <= j) {
      lz[p] += v;
      push(p, l, r);
      return;
    }
    
    int mid = (l+r)/2;
    
    update(2*p, l, mid, i, j, v);
    update(2*p + 1, mid + 1, r, i, j, v);
    st[p] = max(st[2*p], st[2*p+1])
   

``