Binary Index Tree Menggunakan Python

Pendahuluan

Binary Index Tree atau sering disebut juga Fenwick Tree adalah struktur data untuk menghitung prefix sums pada array of numbers dengan fitur data update yang efisien. Untuk informasi lebih lengkap dapat lihat di: https://en.wikipedia.org/wiki/Fenwick_tree

Dalam computer vision, Fenwick Tree digunakan untuk menghitung prefix sum pixel intensities, contoh Viola-Jones face detection algorithm with Haar-features.

Prefix Sums dan Solusi Sederhana

Misalnya kita memiliki array seperti berikut

-1

-3

Array Sample

Maka prefix sum untuk range [0:4] = 3 + 2 -1 + 6 + 5 = 15

Pendekatan sederhana yang dapat dilakukan untuk menghitung prefix sums adalah dengan membuat array baru berisi nilai prefix sums. Dimana index ke i berisi sum dari item sebelumnya.

Array Prefix Sum

Berikut pertimbangan pendekatan diatas

Membuat array prefix sums memerlukan O(n) time.
Mencari prefix sum memerlukan O(1) time.
Update akan memerlukan O(n) time, karena kita harus me-reconstruct array tersebut.

Pendekatan membuat array berisi prefix sum cocok digunakan jika array tidak akan diupdate dan ukuran array kecil.

Note: Dengan pendekatan Fenwick Tree, proses update hanya memerlukan O(log n) time.

Fenwick Tree / Binary Index Tree

Fenwick Tree menggunakan binary representation dari numbers dan indexes.

Digunakan binary karena sangat cepat dalam melakukan binary operation seperti AND dan OR logical operations.

Contoh kita ingin menghitung 10 angka prefix sum:

10 =  2³ + 2¹

sum dari 10 angka sebelumnya dihitung dengan sum 8 angka sebelumnya dan sum 2 angka sesudahnya.

Untuk jelasnya mari kita gunakan array diatas untuk membuat Fenwick Tree.

Pertama kita hitung prefix sum dengan binary range, karena besar array hanya 11, maka binary range yang digunakan adalah 1, 2, 4 dan 8.

Berikutnya kita lakukan proses diatas untuk menghitung prefix sum untuk bagian yang terlewat array index 3, 5, 6, 7, 9, 10, 11.

Karena pada index 3, pada bagian tersebut hanya terdapat satu item, maka digunakan binary index range 1 saja.

Sementara pada interval 5,6,7 dan 9,10,11 digunakan binary range 1 dan 2. Dari proses ini akan tersisa array index 7 dan 11, yang akan dilakukan proses perhitungan pada tahap berikutnya.

Kita akan menggunakan gambar diatas untuk menjelaskan cara menghitung prefix sum.

Hasil dari proses perhitungan diatas, kita simpan array 1 dimensi.

-1

-3

Array Fenwick Tree/ Binary Index Tree

Perhatikan, array Fenwick Tree adalah ukuran original array + 1, dimana index ke 0 akan berisi nilai 0.

Dari array Fenwick Tree, kita dapat bentuk Fenwick Tree seperti berikut:

Dimana child parent relationship dibuat dengan proses:

Perhitungan binary representation dari node index.
Melakukan flip the right-most 1 menjadi 0, yang akan menunjukan index parent node dalam bentuk binary.

Contoh Index 0 adalah parent dari Index 4.

Index 4 dalam binary adalah 0100, di flip menjadi 0000, berarti parent adalah index 0.

Agar lebih jelas, contoh index 4 adalah parent dari index 5.

Index 5 dalam binary adalah 0101. Di flip menjadi 0100, dimana 0100 adalah 4 dalam decimal. Maka index 5 memiliki parent index 4.

Menghitung Prefix Sum Menggunakan Fenwick Tree

Contoh hitung prefix sum untuk index 4. Index 4 dalam perhitungan binary adalah 2², oleh karena itu digunakan single range yaitu [1,4], yaitu akan berisi nilai 10.

Contoh kedua hitung prefix sum untuk index 11. Index 11 dalam perhitungan binary adalah 2³ + 2¹ + 2⁰, oleh karena itu digunakan 3 range yaitu, [1,8], [9,10] dan [11, 11], dimana masing-masing akan berisi value 19, 9 dan 3 dimana akan berjumlah 31.

Proses menghitung prefix sum dalam Fenwick Tree:

Mulai dari index yang dimaksud.
Hitung parent dari index yang dimaksud.
Lakukan proses mencari parent sampai mencapai root node (index 0).

Maka pada contoh perhitungan prefix sum index 11, mulai dari node index 11, kemudian cari parentnya yaitu node index 10, dari index 10 cari parentnya yaitu index 8. Proses mencari parent akanberhenti karena parent dari index 8 adalah 0. Jumlahkan value dari node tersebut, maka akan diperoleh nila prefix sum dari index 11.

Cara Menghitung Parent Index

Pertama kita cari right most 1 (sering disebut last set bit), kemudian gunakan untuk mengurangi original x.

x - ( x &(-x) )

Cara Mengupdate Entry Pada Fenwick Tree

Pertama mulai dari index yang dimaksud, kemudian update semua node yang memiliki index tersebut.

Jadi kita harus dapat mencari next node dengan cara

Cari right-most 1, kemudian tambahkan terhadap index itu sendiri.

x + ( x &(-x) )

Contoh, kita akan mengupdate array index 5 menjadi 7, maka node yang harus diupdate adalah node yang mengandung index 5, yaitu [5,5], [5,6] dan [1,8].

Mulai dari index 5, dalam binary adalah 0101 + 0001 = 0110, yaitu index 6.
Kemudian dari index 6, dalam binary adalah 0110 + 0010 = 1000, yaitu index 8.

Dimana masing-masing node harus ditambah 2 ( 5+ 2 = 7). Jadi node [5, 5] diupdate menjad 7, node [5,6] menjadi 11, node [1,8] menjadi 21.

Implementasi dalam Python

#Fenwick tree or binary indexed tree
class FenwickTree:

	def __init__(self,nums):
		#original array of numbers (integers)
		self.nums = nums
		#the constructed Fenwick tree (first item is 0 always so the size is greater)
		#initialize the values to be 0s
		self.fenwick_tree = [0 for _ in range(len(nums)+1)]
		
	#the sum of numbers in the interval [start:end]
	#O(logN) running time complexity
	def range_sum(self,start,end):
		return self.sum(end)-self.sum(start-1)
		
	#sum of the integers in the range [0:index]
	#O(logN) running time complexity
	def sum(self,index):
	
		#indexes start with 0 but in the theory/implementation we start with 1
		index = index + 1
		#the final result (so the sum of the integers)
		sum = 0
		
		#we may consider the sum of multiple ranges so we have to iterate until index>0
		while index>0:
			#binary index tree contains the sums of given ranges
			sum = sum + self.fenwick_tree[index]
			#go to the parent and keep going (basically the items on the left)
			index = self.parent(index)
			
		return sum

	#constructing the Fenwick tree from the original array of integers
	#O(NlogN) running time complexity
	def construct(self):

		#consider all the items in the original array
		for index in range(1,len(self.nums)+1):
			self.update(index,self.nums[index-1])

	#update an existing item in the tree with index and value accordingly
	#O(logN) running time complexity
	def update(self,index,num):
		
		#have to check all the ranges that include the index
		while index<len(nums)+1:
			self.fenwick_tree[index] += num
			#index of the items on the right
			index = self.next(index)
	
	#index of the item on the left
	#O(1) running time complexity
	def next(self,index):
		return index + (index&-index)

	#index of the item on the right (so the parent)
	#O(1) running time complexity
	def parent(self,index):
		return index - (index&-index)
		
if __name__ == "__main__":
	
	nums = [3,2,-1,6,5,4,-3,3,7,2,3]
	
	fenwick_tree = FenwickTree(nums)
	fenwick_tree.construct()
	
	print(fenwick_tree.range_sum(2,5))

Jika dijalankan kode diatas akan menghasilkan nilai 14.

Sharing is caring: