資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++ 中的二叉索引樹或 Fenwick 樹？
與普通的數字陣列相比，Fenwick 樹在元素更新和字首和計算這兩個操作之間取得了更好的平衡。對於一個包含 m 個數字的普通陣列，我們可以儲存元素本身，或者儲存字首和。在第一種情況下，計算字首和需要線性時間；在第二種情況下，修改或更新陣列元素需要線性時間（在這兩種情況下，另一個操作都可以在常數時間內完成）。Fenwick 樹允許這兩個操作都在 O(log m) 時間內完成。這是透過將數字表示為樹來實現的，其中每個節點的值被視為其子樹中數字的總和。這種樹結構允許僅使用 O(log m) 次節點訪問來完成操作。
透過考慮一個基於 1 的陣列，最容易理解 Fenwick 樹。每個索引 j 為 2 的冪的元素包含前 j 個元素的總和。索引表示兩個（不同）2 的冪之和的元素包含自前一個 2 的冪以來的元素的總和。基本上，每個元素包含自其在樹中的父節點以來的值的總和，並且可以透過清除索引中的最小或最低有效位來找到該父節點。
要計算直到任何給定位置或索引的總和，請考慮位置或索引的二進位制展開，並新增對應於二進位制形式中每個 1 位的元素。
例如，假設要計算前十一個值的總和。十一個是二進位制的 1011。這包含三個 1 位，因此必須新增三個元素：1000、1010 和 1011。這些分別包含 1-8、9-10 和 11 的值的總和。
下面是一個簡單的 C 實現。
示例
#define LSB(i) ((i) & -(i)) // zeroes all the bits except the minimum or least significant one
int A1[SIZE];
int sum(int i) // Returns the sum from index 1 to i{
int sum = 0;
while (i > 0)
sum += A1[i], i -= LSB(i);
return sum;
}
void add(int i, int k) // Adds k to element with index i{
while (i < SIZE)
A1[i] += k, i += LSB(i);
}
更新於：2020年1月29日
309 次瀏覽
廣告