Wiki: Pohon Fenwick atau pohon berindeks biner (BIT) adalah struktur data yang dapat memperbarui elemen secara efisien dan menghitung jumlah awalan dalam sebuah tabel angka.

Fenwick Tree, juga dikenal sebagai Binary Indexed Tree (“BIT”), adalah struktur data yang menyediakan cara efisien untuk melakukan kueri rentang dan pembaruan titik pada array. Ini sangat berguna untuk memecahkan masalah yang memerlukan jumlah kumulatif atau jumlah awalan dalam array yang bisa diubah.

Fenwick Tree memanfaatkan representasi biner dari bilangan bulat dan bit paling tidak signifikannya. Ide utamanya adalah untuk memelihara pohon di mana setiap node bertanggung jawab atas serangkaian elemen dalam array asli, sehingga memungkinkan pembaruan dan kueri rentang yang efisien.

Masalah:



Penjumlahan Kubus | HackerRank
Tentukan Matriks 3-D yang setiap bloknya berisi 0 pada awalnya. Blok pertama ditentukan oleh koordinat (1,1,1) dan…www.hackerrank.com



Solusinya (sederhana):

def update_cube(cube, x, y, z, w):
    """
    Update the value of block (x, y, z) to W.
    """
    cube[x][y][z] = w

def query_cube(cube, x1, y1, z1, x2, y2, z2):
    """
    Compute the sum of the values in the cube between the points (x1, y1, z1) and (x2, y2, z2), inclusive.
    """
    total_sum = 0
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            for k in range(z1, z2+1):
                total_sum += cube[i][j][k]
    return total_sum

def cubeSum(n, operations):
    """
    Process the given operations and return a list of results.
    """
    results = []
    # Initialize the cube with zeros
    cube = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
  
    for operation in operations:
        op_type = operation[0]
        if op_type == "UPDATE":
            x, y, z, w = map(int, operation[1:])
            # Subtract 1 from x, y, and z to convert from 1-based indexing to 
            # 0-based indexing
            update_cube(cube, x-1, y-1, z-1, w)
        elif op_type == "QUERY":
            x1, y1, z1, x2, y2, z2 = map(int, operation[1:])
            # Subtract 1 from x1, y1, z1, x2, y2, and z2 to convert from 
            # 1-based indexing to 0-based indexing
            total_sum = query_cube(cube, x1-1, y1-1, z1-1, x2-1, y2-1, z2-1)
            results.append(total_sum)

    return results

Penjelasan:

Perlu diingat bahwa solusi sederhana ini sangat mudah.

Kami menginisialisasi kubus dengan nol.

Kami memeriksa setiap jenis operasi, tergantung pada apakah itu UPDATE: kami memperbarui nilai kubus pada koordinat tertentu (x,y,z), jika itu adalah QUERY: kami harus menjumlahkan semua nilai koordinat kubus.

Variabel x1, y1, z1, x2, y2, dan z2 adalah koordinat dua sudut berlawanan dari sub-kubus yang ingin Anda hitung jumlah nilainya. Secara khusus, (x1, y1, z1) mewakili koordinat minimum x, y, dan z, dan (x2, y2, z2) mewakili koordinat maksimum x, y, dan z dari sub-kubus.

map digunakan untuk mengubah nilai dari stringmenjadi integer.

Bergantung pada waktu dan daya komputasi Anda, solusi ini akan bekerja 100% sepanjang waktu.

Rincian kode secara rinci:

  1. Fungsi update_cube(cube, x, y, z, w): Fungsi ini memperbarui nilai blok pada koordinat (x, y, z) yang diberikan menjadi w.
  2. Fungsi query_cube(cube, x1, y1, z1, x2, y2, z2): Fungsi ini menghitung jumlah nilai dalam kubus antara titik (x1, y1, z1) dan (x2, y2, z2) (keduanya inklusif). Ia menggunakan tiga loop bersarang untuk mengulangi semua elemen dalam sub-kubus dan menghitung jumlah nilainya.
  3. Fungsi cubeSum(n, operations): Fungsi ini memproses operasi yang diberikan dan mengembalikan daftar hasil. Ini menginisialisasi kubus 3D dengan dimensi (n, n, n) dan mengulangi operasi. Jika operasinya adalah 'UPDATE', ia memperbarui kubus dengan nilai baru. Jika operasinya adalah 'QUERY', operasi ini menghitung jumlah total antara koordinat yang diberikan menggunakan fungsi query_cube() dan menambahkan hasilnya ke daftar hasil.

Solusinya (Fenwick):

class FenwickTree3D:
    def __init__(self, n):
        self.size = n
        # Initialize the 3D Fenwick Tree with dimensions (n+1, n+1, n+1) and fill it with zeros
        self.tree = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

    def update(self, x, y, z, value):
        # Update the Fenwick Tree with the given value at the specified (x, y, z) coordinate
        while x <= self.size:
            y1 = y
            while y1 <= self.size:
                z1 = z
                while z1 <= self.size:
                    self.tree[x][y1][z1] += value
                    z1 += z1 & -z1  # Update z1 index for the next iteration
                y1 += y1 & -y1  # Update y1 index for the next iteration
            x += x & -x  # Update x index for the next iteration

    def query(self, x, y, z):
        # Calculate the sum of values in the cube from the origin (1, 1, 1) to the specified (x, y, z) coordinate
        result = 0
        while x > 0:
            y1 = y
            while y1 > 0:
                z1 = z
                while z1 > 0:
                    result += self.tree[x][y1][z1]
                    z1 -= z1 & -z1  # Update z1 index for the next iteration
                y1 -= y1 & -y1  # Update y1 index for the next iteration
            x -= x & -x  # Update x index for the next iteration
        return result

def cubeSum(n, operations):
    results = []
    # Initialize a 3D Fenwick Tree with size n
    fenwick_tree = FenwickTree3D(n)

    for operation in operations:
        op_type = operation[0]
        if op_type == "UPDATE":
            x, y, z, w = map(int, operation[1:])
            # Calculate the previous value at the given coordinate
            prev_value = fenwick_tree.query(x, y, z) - fenwick_tree.query(x - 1, y, z) - \
                         fenwick_tree.query(x, y - 1, z) - fenwick_tree.query(x, y, z - 1) + \
                         fenwick_tree.query(x - 1, y - 1, z) + fenwick_tree.query(x - 1, y, z - 1) + \
                         fenwick_tree.query(x, y - 1, z - 1) - fenwick_tree.query(x - 1, y - 1, z - 1)
            # Update the Fenwick Tree with the difference between the new value and the previous value
            fenwick_tree.update(x, y, z, w - prev_value)
        elif op_type == "QUERY":
            x1, y1, z1, x2, y2, z2 = map(int, operation[1:])
            # Calculate the range sum between the given coordinates using the inclusion-exclusion principle
            total_sum = fenwick_tree.query(x2, y2, z2) - fenwick_tree.query(x1 - 1, y2, z2) - \
                        fenwick_tree.query(x2, y1 - 1, z2) - fenwick_tree.query(x2, y2, z1 - 1) + \
                        fenwick_tree.query(x1 - 1, y1 - 1, z2) + fenwick_tree.query(x1 - 1, y2, z1 - 1) + \
                        fenwick_tree.query(x2, y1 - 1, z1 - 1) - fenwick_tree.query(x1 - 1, y1 - 1, z1 - 1)
            results.append(total_sum)
      return results

Seperti yang mungkin sudah Anda ketahui, kami menggunakan OOP (pemrograman berorientasi objek) untuk solusi kedua ini.

OOP dipilih karena manfaatnya:

encapsulation: struktur data pohon Fenwick dan metode terkaitnya (pembaruan dan kueri) dienkapsulasi dalam kelas FenwickTree3D. Hal ini membuat kode tetap teratur, dan data serta metode digabungkan menjadi satu, sehingga lebih mudah untuk dipahami dan dipelihara.

Pendekatan modularity: memungkinkan Anda membuat modul terpisah untuk kelas FenwickTree3D. Anda dapat menggunakan kembali modul ini dalam masalah atau proyek lain yang memerlukan Pohon Fenwick 3D tanpa mengubah implementasi inti.

code clarity: membantu membuat kode lebih mudah dibaca dan dipahami. Kelas mendefinisikan antarmuka yang jelas untuk struktur data, dan metode di dalam kelas bertanggung jawab untuk tugas spesifik yang terkait dengan Pohon Fenwick. Hal ini memudahkan untuk mengikuti logika kode dan memahami bagaimana struktur data digunakan.

Sekarang mari kita berjalan-jalan sebentar di jalur kenangan.

Pemrograman Berorientasi Objek (OOP) adalah paradigma pemrograman yang menggunakan “objek” untuk memodelkan entitas dunia nyata dan interaksinya. Objek adalah turunan dari kelas, yang merupakan templat yang mendefinisikan properti dan metode objek tersebut.

Prinsip:

  1. Enkapsulasi: adalah proses menggabungkan data (properti) dan fungsi (metode) yang mengoperasikan data dalam satu unit, yang disebut kelas. Hal ini menyembunyikan cara kerja internal suatu kelas dari dunia luar dan membantu menjaga integritas keadaan objek. Enkapsulasi mendorong pemisahan masalah, membuat kode lebih mudah dipahami, dipelihara, dan di-debug.
  2. Warisan: adalah mekanisme yang memungkinkan satu kelas mewarisi properti dan metode kelas lain, sehingga mendorong penggunaan kembali kode. Kelas yang diwarisinya disebut “parent” atau “superclass”, dan kelas yang mewarisinya disebut “child” atau “subclass”. Subkelas dapat mengesampingkan atau memperluas properti dan metode superkelas, memungkinkan perilaku khusus sambil tetap mendapatkan manfaat dari fungsionalitas bersama.
  3. Polimorfisme: mengacu pada kemampuan objek yang termasuk dalam kelas berbeda untuk diperlakukan sebagai objek dari superkelas yang sama. Hal ini memungkinkan satu antarmuka untuk mewakili berbagai jenis objek, memungkinkan kode menjadi lebih fleksibel dan mudah beradaptasi. Polimorfisme dicapai melalui pewarisan dan dapat mengambil dua bentuk: kelebihan metode (menggunakan nama metode yang sama dengan parameter berbeda) dan penggantian metode (mendefinisikan ulang metode dalam subkelas).
  4. Abstraksi: adalah proses menyederhanakan sistem yang kompleks dengan memecahnya menjadi bagian-bagian yang lebih kecil dan lebih mudah dikelola. Dalam OOP, hal ini dicapai dengan membuat kelas dan antarmuka abstrak yang memberikan tampilan sistem tingkat tinggi yang sederhana sambil menyembunyikan detail implementasi yang mendasarinya. Abstraksi memungkinkan pengembang untuk fokus pada fitur-fitur penting dari suatu masalah tanpa terjebak dalam kompleksitas sistem.

Penjelasan:

Fenwick Tree, juga dikenal sebagai Binary Indexed Tree (BIT), adalah struktur data yang menyediakan cara efisien untuk melakukan kueri rentang dan pembaruan titik pada array. Ini sangat berguna untuk memecahkan masalah yang memerlukan jumlah kumulatif atau jumlah awalan dalam array yang bisa berubah.

Fenwick Tree memanfaatkan representasi biner dari bilangan bulat dan bit paling tidak signifikannya. Ide utamanya adalah untuk memelihara pohon di mana setiap node bertanggung jawab atas serangkaian elemen dalam array asli, sehingga memungkinkan pembaruan dan kueri rentang yang efisien.

Pohon Fenwick memiliki kompleksitas waktu O(log n) untuk pembaruan dan kueri rentang, yang lebih baik daripada pendekatan naif O(n) saat melakukan beberapa operasi pada array. Ini juga lebih hemat ruang dibandingkan dengan struktur data lain seperti pohon segmen.

Sekarang mari kita telusuri kodenya:

  1. FenwickTree3Dclass: Kita mendefinisikan kelas Pohon Fenwick 3D, yang merupakan generalisasi dari Pohon Fenwick 1D. Konstruktor menginisialisasi pohon 3D dengan dimensi (n+1, n+1, n+1) diisi dengan nol. Kami menggunakan n+1bukannya nuntuk menangani pengindeksan berbasis 1 untuk koordinat kubus.
  2. update()method: Metode ini memperbarui nilai pada titik tertentu (x, y, z) di pohon. Kami menggunakan loop bersarang untuk melintasi pohon di setiap dimensi. Loop menggunakan operasi AND bitwise (&) untuk menentukan indeks berikutnya yang akan diperbarui, yang merupakan fitur penting dari Fenwick Tree.
  3. query()metode: Metode ini menghitung jumlah nilai dalam kubus dari titik asal (1, 1, 1) hingga titik tertentu (x, y, z). Mirip dengan metode pembaruan, metode ini menggunakan loop bersarang dan operasi bitwise untuk melintasi pohon dan mengumpulkan jumlahnya.
  4. Fungsi cubeSum(): Fungsi ini mengambil ukuran kubus (n) dan daftar operasi yang akan dilakukan. Ini menginisialisasi instance FenwickTree3D dan melakukan iterasi melalui operasi. Jika operasinya adalah “UPDATE”, ia menghitung nilai sebelumnya pada koordinat yang diberikan dan memperbarui pohon dengan perbedaan antara nilai baru dan nilai sebelumnya. Jika operasinya adalah “QUERY”, operasi ini menghitung jumlah rentang menggunakan metode kueri dan memanfaatkan prinsip inklusi-eksklusi untuk menentukan jumlah antara dua titik tertentu dalam kubus.

Kesimpulan: solusi umum vs solusi Fenwick

Pohon Fenwick memiliki kompleksitas waktu O(log n) untuk pembaruan dan kueri rentang, yang lebih baik daripada pendekatan naif O(n) saat melakukan beberapa operasi pada susunannya. Ini juga lebih hemat ruang dibandingkan dengan struktur data lain seperti pohon segmen.

Terima kasih telah membaca dan atas dukungan Anda.

Jika ada yang kurang jelas atau Anda kesulitan, silakan menghubungi Medium atau LinkedIn.