前言

真心希望各位dalao點贊+收藏~

樹狀數組

作用：高效求出區間前綴和，允許進行修改操作。 舉個栗子： 剛開始有8項，分別為1-8。 首先構建二叉樹：

			   1-8/ |/  |/   |/    |/     |1-4     5-8/ |	    / |/  |    /  |1-2 3-4 5-6 7-8/ | / | / | / |1  2 3 4 5 6 7 8

設x為第i個數所在的層數，顯然2,4,6,8,3-4,7-8沒有任何用處，因為其他t[i]（僅需<個）表示樹狀數組去掉不需要的數組后第i項的值。

void add(int x,int p){while(x<=n){c[x]+=p;//x為下標，c[x]包含x[原來初始的下標x] x+=lowbit(x);//lowbit為轉成二進制從后往前第一個為1的值(那一位的權值)}
}

（暴力求解，每次輸入一個值都進行如上時間復雜度為O(log n)的操作（只加了當前這個值），時間復雜度O(n log n)，空間復雜度O(n)）?

void build(){for(int i=1;i<=n;i++){t[i]+=a[i];//t[i]肯定包含a[i]，而且以前一定沒加上，所以要加上t[i+(i&-i)/*相當于lowbit(i)*/]+=t[i];//直接加到上級祖先}
}

（優化求解，直接一次性加給他的祖先，時間復雜度O(n)，空間復雜度O(2n)）?

以上兩種建樹方法各有優劣，相當于一個時間空間互換的過程。?

拓展類型1： 1.求逆序數（對）問題 逆序數是指在第i個數前有多少個>第i個數的數。

樹狀數組的作用是求出前綴和， 所以我們可以使用類似于桶排序的原理，桶[i]表示i在此時出現的次數。

只需要求第i個數的時候就把桶[第i個數]++就可以了。

PS:一般用離散化使其空間復雜度變小且下標連續。