Array prefix sum menjawab total rentang dalam O(1), tetapi satu nilai yang berubah memaksa Anda membangun ulang O(n) bagian darinya. Fenwick tree, juga disebut binary indexed tree, mengorbankan sedikit kecepatan query demi pembaruan yang cepat: keduanya berbiaya O(log n).
Idenya muat dalam dua perulangan. Sel tree[i] menyimpan total dari i & -i nilai terakhir yang berakhir pada posisi i, dengan i & -i adalah bit terendah yang bernilai 1 pada i. Untuk menambah pada posisi i, naiklah dengan i += i & -i, menyentuh setiap sel yang mencakupnya. Untuk membaca prefix sampai i, turunlah dengan i -= i & -i sambil menjumlahkan sel-sel yang saling lepas. Tree dimulai dari indeks 1 karena 0 tidak memiliki bit terendah yang bernilai 1.
Gunakan Fenwick tree saat nilai berubah di antara pertanyaan prefix atau jumlah rentang, atau saat Anda menghitung sesuatu "sejauh ini" berdasarkan nilai: skor sebelumnya yang berada di bawah skor ini, atau timestamp sebelumnya yang berada di atasnya. Jika digabungkan dengan difference array, tree ini juga menangani pembaruan rentang dengan pencarian titik. Untuk minimum, maksimum, atau penggabungan yang lebih kompleks, gunakan segment tree.
Pembaruan naik sesuai bit terendah yang bernilai 1; pembacaan prefix turun sesuai bit itu.