Basic Update-Query di Tree

Setelah sekian lama tidak ada aktivitas, akhirnya ada post \ :v / Maafkan saya yang suka menunda-nunda pekerjaan :')

Pada post kali ini, saya mau cerita sedikit tentang menggunakan struktur data di tree. Sesuai judul, basic. Artinya saya gak akan nulis tentang Heavy-Light Decomposition atau Centroid Decomposition atau sejenisnya. Capek soalnya

Apa Yang Kita Butuhkan?

• Struktur data seperti segment tree atau fenwick tree
• Teknik mencari lowest common ancestor (LCA)
• (?) Pre-order numbering

Struktur data seperti segment tree atau fenwick tree sudah banyak pembahasannya, saya sendiri juga pernah sedikit mengulas fenwick tree. Untuk LCA, saya sarankan membaca tutorial Topcoder, biasanya saya menggunakan binary lifting atau gampangnya sparse table. Di blog ini yang akan dibahas Pre-order numbering

Pre-order Numbering 

Pada tree, ada penelusuran yang disebut pre-order traversal. Kita membutuhkan teknik itu untuk memberi "nomor masuk" dan "nomor keluar" setiap node. "nomor masuk" adalah urutan masuk ke node tersebut, sedangkan "nomor keluar" adalah urutan masuk node yang terakhir dikunjungi pada subtree tersebut. Kurang lebih, contohnya adalah seperti ini:
 

Masuk|Keluar

Bagaimana cara membuat array in[] dan out[] ? Kita bisa menggunakan cara seperti potongan code berikut:

int cntr = 0;
int in[MAXN];
int out[MAXN];

void dfs(int now,int prv) {
    in[now] = ++cntr;
    for(int nxt : adj[now]) {
        if(nxt == prv) continue;
        dfs(nxt,now)
    }
    out[now] = cntr;
}
 

Nah, terus apa gunanya penomoran itu? Perhatikan, misal kita representasikan tiap node dengan in[] nya. Apa yang bisa kita simpulkan dari in[] dan out[] ? Yup, tiap rentang [in[a], out[a]] merupakan interval suatu subtree! Biasanya saya sebut "gepengin pohonnya". Karena kita sekarang punya interval, artinya kita bisa menggunakan bantuan struktur data seperti segment tree atau fenwick tree!

Bekerja di Subtree

Tadi kita sudah tahu bahwa dengan bantuan dua array, kita bisa mengubah suatu subtree menjadi suatu interval. Langsung ke contoh soal ya, SPOJ - Palindrome in a Tree

Pertama-tama, kita harus tahu ciri-ciri string yang bisa dijadikan palindrom. Hal yang penting, kita lihat paritas (gak tau istilah benarnya apaan) tiap karakter string itu. Jika yang ganjil = 0, kita pasti bisa buat palindrome. Jika yang ganjil = 1, kita bisa buat yang paritasnya ganjil itu jadi di tengah string, dan selanjutnya kita bisa membuat palindrom.  Selain itu, pasti tidak ada cara.

Jadi, kita cuma perlu tahu paritas tiap karakter dalam satu subtree. Bagaimana caranya? Kita bisa memakai fakta bahwa paritas hanya 0/1, yang bisa kita representasikan menggunakan biner. Artinya, kita bisa membuat bitmask berukuran 26.

Eksekusinya bagaimana? Kita bisa menggunakan point-update untuk mengubah suatu nilai (ingat kita pakai in[] sebagai indeks). Selanjutnya, untuk mengetahui paritas suatu subtree, kita bisa meng-query paritas pada interval subtree tersebut.

Bagaimana cara menggabungkan paritas? Bitmask berukuran 26 bisa direpresentasikan menggunakan int, dan ketika kita menggabungkan, sebenarnya kita melakukan operasi xor.

Contoh solusi:

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int BIT[N];
int in[N],ot[N];
vector<int> adj[N];
int sz;
int n,q;
char s[N];

// pre-order numbering
void dfs(int now,int prv) {
 in[now] = ++sz;
 
 for(int nex : adj[now]) {
  if(nex == prv) continue;
  dfs(nex,now);
 }
 
 ot[now] = sz;
}

// update paritas pakai xor
void update(int x,int val) {
 val = 1 << val;
 for(; x <= n ; x += x & -x)
  BIT[x] ^= val;
}

int query(int x) {
 int res = 0;
 while(x) {
  res ^= BIT[x];
  x -= x & -x;
 }
 return res;
}

int main() {
 scanf("%d",&n);
 for(int i = 1 ; i < n ; i++) {
  int u,v;
  scanf("%d %d",&u,&v);
  adj[u].push_back(v);
  adj[v].push_back(u);
 }
 
 dfs(1,0);
 scanf("%s",s);
 for(int i = 1 ; i <= n ; i++)
  update(in[i],s[i - 1] - 'a');
 
 scanf("%d",&q);
 for(int i = 0 ; i < q ; i++) {
  int tipe,x;
  scanf("%d %d",&tipe,&x);
  if(tipe == 1) {
   int res = query(ot[x]) ^ query(in[x] - 1);
   // jika yang ganjil <= 1, maka bisa
   printf("%s\n", __builtin_popcount(res) <= 1 ? "YES" : "NO");
  }
  else {
   char ch[3];
   scanf("%s",ch);
   // pertama-tama, "hapus" kemunculan karakter dulu
   update(in[x],s[x - 1] - 'a');
   s[x - 1] = ch[0];
   // "tambahkan" kemunculan karakter baru
   update(in[x],s[x - 1] - 'a');
  }
 } 
 return 0;
}

Ini hanya salah satu aplikasi pre-order + struktur data untuk menyelesaikan persoalan update-query pada subtree. Terkadang, soalnya bisa saja butuh range-update point-query. Intinya, jika anda sudah lancar melakukan operasi-operasi tersebut pada struktur data, anda tinggal latihan sedikit agar bisa memahami penggunaan in[] dan out[]. Oh iya, terkadang juga, anda butuh lebih dari 1 struktur data untuk menyelesaikannya.

Soal yang bisa dijadikan latihan:
SPOJ - Palindrome in Tree (dibahas pada blog ini)
SPOJ - Snail family problems (Ada 2 kasus untuk update!) 
SPOJ - Rooted Trees (butuh lebih dari satu fenwick tree)
SPOJ - Salary Management (Agak ribet)
Codeforces - On Changing Tree (lebih simple dari Rooted Trees)

Bekerja di Path

Wut? Path? Bukannya cuma bisa pake heavy-light decomposition?

Yang akan saya bahas di sini adalah operasi update dan query, yang memiliki inverse (seperti penjumlahan, xor, perkalian). Trik yang akan saya bahas ini tidak bisa diaplikasikan pada update dan query sepert max dan min.

Saya sebenarnya hampir tidak memiliki contoh soal untuk teknik ini. Teknik ini saya temukan secara tidak sengaja waktu mencoba mengerjakan UVa- Lightning Energy Report. Dulu, ketika Pelatnas, saya mengerjakannya dengan HLD. Namun, ketika nganggur, saya coba mikir apa yang bisa saya lakukan jika ada pertanyaan "berapa nilai node x?" secara online. HLD? Males, ribet. Waktu ngutak-atik, ternyata jika yang ditanya hanya nilai satu node, kita bisa menggunakan fenwick tree saja! 

Bagaimana caranya? Pertama-tama, kita harus tahu cara mengupdate path root -- u untuk tiap node u. Caranya? Ingat bahwa interval [in[v],out[v]] menyatakan interval subtree node v. Seandainya kita ingin mengupdate semua nilai ancestor u dan u itu sendiri, apa yang harus kita lakukan?

Coba update(in[u],value). Observasi apa yang terjadi. Seandainya kita melakukan query(in[v],out[v]) untuk mencari nilai node v, maka node-node yang nilainya terkena efek update(in[u],value) hanyalah ancestor dari u serta u itu sendiri!

Resapi baik-baik paragraf sebelumnya.

Kemudian, bagaimana caranya meng-extend ke path u-v untuk sembarang u dan v? Pertama, jelas kita melakukan update(in[u],value) dan update(in[v],value). Oh tidak, pada LCA(u,v), nilainya ketambah 2 kali. Untuk menghilangkan, lakukan update(in[LCA(u,v)],-value). Tapi, ancestor dari
LCA(u,v) juga masih ketambahan value, padahal mereka harusnya tidak kena update. Yaudah, kita lakukan update(in[parent[ LCA(u,v) ] ], -value).

Contoh solusi:  

#include <bits/stdc++.h>
using namespace std;

const int N = 50005;
const int LOG = 16;

vector<int> adj[N];
int anc[N][LOG];
int depth[N];

int in[N], ot[N];
int sz;

int BIT[N];
int n,q;

void update(int x,int val) {
 // bisa saja terjadi
 // kalau ada pemanggilan update parent[root]
 if(x == 0) return;
 for(; x <= n ; x += x & -x)
  BIT[x] += val;
}

int query(int x) {
 int ret = 0;

 while(x) {
  ret += BIT[x];
  x -= x & -x;
 }

 return ret;
}

int getLCA(int u,int v) {
 if(depth[u] < depth[v]) swap(u,v);
 int diff = depth[u] - depth[v];

 for(int i = 0 ; diff > 0 ; i++)
  if(diff & (1 << i)) {
   u = anc[u][i];
   diff -= (1 << i);
  }

 if(u == v) return u;

 for(int i = LOG - 1 ; i >= 0 ; i--)
  if(depth[u] >= (1 << i) && anc[u][i] != anc[v][i]) {
   u = anc[u][i];
   v = anc[v][i];
  } 

 return anc[u][0]; 
}

void read() {
 scanf("%d",&n);
 for(int i = 1 ; i < n ; i++) {
  int u,v;
  scanf("%d %d",&u,&v);

  // bikin 1-based
  u++; v++;
  adj[u].push_back(v);
  adj[v].push_back(u);
 }
}

void build_table(int now,int par) {
 anc[now][0] = par;
 depth[now] = depth[par] + 1;

 for(int i = 1 ; (1 << i) <= depth[now] ; i++) {
  int papa = anc[now][i - 1];
  int grandpa = anc[papa][i - 1];
  anc[now][i] = grandpa;
 }
}

void dfs(int now,int prv) {
 in[now] = ++sz;

 for(int nex : adj[now]) {
  if(nex == prv) continue;
  build_table(nex,now);
  dfs(nex,now);
 }

 ot[now] = sz;
}

void make_tree() {
 dfs(1,-1);
}

void update(int u,int v,int val) {
 int lca = getLCA(u,v);

 // update u sama v
 update(in[u],val);
 update(in[v],val);

 // hilangin ketambahan 2 kali
 update(in[lca],-val);
 int par = anc[lca][0];
 // hilangin ketambahan
 update(in[par],-val);
}

void solve() {
 scanf("%d",&q);
 for(int i = 0 ; i < q ; i++) {
  int u,v,val;
  scanf("%d %d %d",&u,&v,&val);

  // bikin 1-based
  u++; v++;
  update(u,v,val);
 }

 for(int i = 1 ; i <= n ; i++)
  printf("%d\n",query(ot[i]) - query(in[i] - 1));
}

void reset() {
 for(int i = 1 ; i <= n ; i++) {
  adj[i].clear();
  BIT[i] = 0;
  depth[i] = 0;
 }
 sz = 0;
}


int main() {
 int t; scanf("%d",&t);

 for(int tc = 1 ; tc <= t ; tc++) {
  printf("Case #%d:\n",tc);
  read();
  make_tree();
  solve();
  reset();
 }
 return 0;
}

Seperti saya singgung sebelumnya, aplikasi teknik ini sangat jarang (atau saya kurang banyak latihan). Tapi, keuntungan teknik ini adalah, tidak perlu ribet-ribet bikin HLD (yay!)

Soal yang bisa dipakai latihan:
UVa - Lightning Energy Report (dibahas di blog ini)
SPOJ - Tours (reduce dulu jadi tree dengan menggunakan tarjan untuk mencari bridge)

Sepengalaman saya, teknik yang sering membantu itu yang pertama, yang query subtree. Tapi, tidak ada salahnya kan memperbanyak "senjata" untuk mengalahkan soal? :D

See you next time~