Sabtu, 06 Desember 2014

Persistent Data Structure

Kali ini saya akan memperkenalkan suatu struktur data yang sangat menarik, yaitu persistent data structure. Struktur data ini sebenarnya adalah modifikasi dari struktur data yang sudah ada, seperti segment tree atau BST. Saya akan menerangkannya mulai dari permasalahan.

Permasalahan Motivasi

Diberikan sebuah array A berisi N bilangan. Indeks dari A dinomori dari 0 sampai N-1. Diberikan pula Q operasi yang bisa berupa:
  • Update x y, yang artinya laksanakan A[x] = y
  • Query x y z, yang artinya cari min(A[x], A[x+1], A[x+2], ..., A[y]) pada array A sebelum operasi update ke-z dilaksanakan

Nah lho, bagaimana jika N dan Q bisa sampai 100.000? Tidak mungkin kita menyimpan setiap versi dari array A kan?

Persistent Segment Tree

Seandainya setiap query dilaksanakan pada array A versi terakhir, maka kita bisa menerapkan struktur data segment tree seperti biasa.

Coba perhatikan versi pertama dari array A. Saya sebut versi ini sebagai "versi 0".

Jika dilakukan update pada A[5], didapatkan versi 1 dari array A. Perhatikan segmen-segmen yang di-update:

Tentu saja, kita kehilangan informasi dari versi 0 array A. Namun, perhatikan lebih lanjut bahwa hanya O(log N) segmen saja yang berubah, sementara sisanya tetap sama.

Jadi, bagaimana kalau dibuat saja "cascading segment tree"? Kita buat segment tree baru, tetapi menggunakan sebagian besar data yang ada pada segment tree versi sebelumnya.


Kita akan menambahkan sebanyak O(log N) node baru pada segment tree yang baru ini. Anak kiri dan anak kanan dari setiap node yang baru ditentukan dari elemen mana yang diubah. Dengan mengingat setiap root node dari setiap versi, kita bisa mendapatkan informasi segment tree untuk setiap versi! Coba saja pandang segment tree yang memiliki root di versi 1!

Kini, setiap update dapat dilaksanakan dalam O(log N) dan menambah kompleksitas memori sebesar O(log N) juga, dan setiap query bisa dilakukan dalam O(log N). Cukup untuk N dan Q hingga ratusan ribu.

Implementasi

Tentu saja ada macam-macam implementasi yang bisa Anda gunakan. Saya menyarankan untuk menghindari penggunaan pointer, karena menambah konstanta yang besar dan mungkin saja algoritma O(N log N) Anda TLE untuk N = 100.000 (saya pernah mengalaminya).

Cara yang saya sarankan adalah membuat semua struct-nya dalam array 1 dimensi, lalu indeksnya menjadi id bagi setiap node. Detilnya bisa dilihat pada implementasi berikut:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cstring>
#include <algorithm>
 
#define INF 2123123123
#define MAXN 132000
#define MAXLG 17
using namespace std;
 
struct node{
   int val;
   int l,r;
};
 
// using maximum O(N log N) nodes
node stri[2*MAXN*MAXLG];
int pnode = 0; // count used nodes
 
int ar[MAXN];
int root[MAXN];
int N,Q;
 
void merge(int u, int x, int y){
   stri[u].val = min(stri[x].val, stri[y].val);
}
 
void build(int nod, int ki, int ka){
   if (ki == ka){
      stri[nod].val = ar[ki];
   }else{
      int tgh = (ki + ka) >> 1;
       
      stri[nod].l = pnode++;
      build(stri[nod].l, ki, tgh);
       
      stri[nod].r = pnode++;
      build(stri[nod].r, tgh+1, ka);
       
      merge(nod, stri[nod].l, stri[nod].r);
   }
}
 
void update(int nod, int ki, int ka, int pnod, int x, int v){
   if (ki == ka){
      stri[nod].val = v;
   }else{
      int tgh = (ki + ka) >> 1;
       
      if (x <= tgh){
         // left: new, right: old
         stri[nod].l = pnode++;
         stri[nod].r = stri[pnod].r;
         update(stri[nod].l, ki, tgh, stri[pnod].l, x, v);
      }else{
         // left: old, right: new
         stri[nod].l = stri[pnod].l;
         stri[nod].r = pnode++;
         update(stri[nod].r, tgh+1, ka, stri[pnod].r, x, v);
      }
       
      merge(nod, stri[nod].l, stri[nod].r);
   }
}
 
int query(int nod, int ki, int ka, int a, int b){
   if ((a <= ki) && (ka <= b)){
      return stri[nod].val;
   }else{
      int tgh = (ki + ka) >> 1;
      int ret = INF;
       
      if (a <= tgh) ret = min(ret, query(stri[nod].l, ki, tgh, a, b));
      if (b >  tgh) ret = min(ret, query(stri[nod].r, tgh+1, ka, a, b));
       
      return ret;
   }
}
 
int main(){
   scanf("%d%d", &N, &Q);
   for (int i = 0; i < N; i++){
      scanf("%d", &ar[i]);
   }
    
   root[0] = pnode++;
   build(root[0], 0, N-1);
    
   int proot = 1;
   for (int i = 0; i < Q; i++){
      char sc[10];
      scanf("%s", sc);
       
      if (sc[0] == 'U'){
         // update
         int x,y;
         scanf("%d %d", &x, &y);
          
         root[proot] = pnode++;
         update(root[proot], 0, N-1, root[proot-1], x, y);
         proot++;
      }else{
         // query
         int x,y,z;
         scanf("%d%d%d", &x, &y, &z);
          
         printf("%d\n", query(root[z-1], 0, N-1, x, y));
      }
   }
}

Generalisasi

Tidak hanya segment tree yang bisa dibuat versi persistent-nya. Struktur data seperti BBST (misalnya AVL atau treap) juga bisa. Silakan perkuat kemampuan implementasi Anda, karena sepengalaman saya tidak mudah untuk mengimplementasikan persistent BBST.

Latihan

Diposting oleh di
Label: , , ,

2 komentar :

  1. Anonim13 Oktober 2015 pukul 15.19

    Penjelasan yang sangat detail! Saya langsung mengerti. Terima kasih banyak m(-_-)m.

    Buat tutorial suffix array dong kak. Atau Max Flow.

    BalasHapus
    Balasan
    1. William Gozali13 Oktober 2015 pukul 23.28

      Halo, syukurlah kalau tulisannya membantu :)

      Untuk suffix array dan max flow, mungkin saya tidak menjelaskan algoritmanya. Di buku competitive programming udah cukup jelas soalnya. Kalau untuk variasi dan penyelesaian soal mungkin akan saya bahas

      Hapus

Langganan: Posting Komentar ( Atom )