image.png
首先樹狀數(shù)組,就是用數(shù)組來模擬樹形結構.
和「堆」一樣敌蚜，樹狀數(shù)組的 0 號下標不放置元素耘眨，從 1 號下標開始使用。
lowbit 函數(shù)
這樣命名的含義是截取一個正整數(shù)的二進制表示里的最低位的 1 和它后面的所有的 0。lowbit 的定義如下：
lowbit(x) = x & (-x);
說明：
這里 x 一定是正整數(shù)，即 x >= 1线得；
這里 & 表示按位與運算；
-x 也可以寫成 (~x + 1) 徐伐，這里 ~ 表示「按位取反」贯钩。這是負數(shù)的定義，負數(shù)用補碼表示办素，它的值等于這個負數(shù)的絕對值按位取反以后再加 11角雷，因此
lowbit(x) = x & (~x + 1);。
單點更新
/**
* 單點更新
*
* @param i 原始數(shù)組索引 i
* @param delta 變化值 = 更新以后的值 - 原始值
*/
public void update(int i, int delta) {
// 從下到上更新性穿，注意勺三，預處理數(shù)組，比原始數(shù)組的 len 大 1需曾，故 預處理索引的最大值為 len
while (i <= len) {
tree[i] += delta;
i += lowbit(i);
}
}
前綴和查詢
/**
* 查詢前綴和
*
* @param i 前綴的最大索引吗坚，即查詢區(qū)間 [0, i] 的所有元素之和
*/
public int query(int i) {
// 從右到左查詢
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
求逆序對的算法題
將離散過的數(shù)據(jù),從后往前放進樹狀數(shù)組里,
當?shù)?i 個數(shù)的時候,即將放進 樹狀數(shù)組 里的時候,后邊比他小的數(shù)已經(jīng)放進他前面的下標里了, 因此只需要把他前面元素的數(shù)量加一塊,就得到后邊有多少比第i個數(shù)小的了
