正文
今天看算法競賽入門指南愈污，看到了一個(gè)叫做《區(qū)間信息的維護(hù)與查詢》的章節(jié)耀态，然后在本章節(jié)的第一小點(diǎn)介紹了一種二叉索引樹的概念，當(dāng)初自學(xué)數(shù)據(jù)結(jié)構(gòu)的時(shí)候?qū)W過暂雹，現(xiàn)在再來看首装。握草？杭跪？２局选；酉隆！完全不知道在說啥桨醋。什么是lowbit棚瘟？？輔助數(shù)組要干嘛喜最？偎蘸？瞎雞兒搞~ 本來想直接跳過，后來想想還是好好學(xué)一把吧瞬内！結(jié)果就懂了~
正文
本文直接借鑒下面的博客進(jìn)行補(bǔ)充：
區(qū)間信息的維護(hù)與查詢（一）——二叉索引樹（Fenwick樹虫蝶、樹狀數(shù)組）
我們有一個(gè)動(dòng)態(tài)連續(xù)和查詢問題：給定一個(gè)n個(gè)元素的數(shù)組A[1]章咧、A[2]、A[3]能真、……A[n]赁严，你的任務(wù)是設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，使得其支持以下兩個(gè)操作：
1：Add（x粉铐，d）操作：讓A[x]增加d疼约；
2：Query（L,R）操作：計(jì)算A[L]+A[L+1]+……+A[R]。
第一種思路就是循環(huán)累加蝙泼，這樣每次的時(shí)間復(fù)雜度都是O（n）級(jí)別的程剥。這樣在數(shù)據(jù)很大的情況之下，是一定會(huì)效率很低的汤踏，所以我們引進(jìn)了二叉索引樹（也就是樹狀數(shù)組）這種比較高級(jí)的數(shù)據(jù)結(jié)構(gòu)织鲸，說它高級(jí)，也高不到那里去溪胶，也就是比原先我們學(xué)過的數(shù)據(jù)結(jié)構(gòu)難一些就是了搂擦。好吧，對我來說初步看的時(shí)候挺難得载荔，自己寫幾下就好多了盾饮。
在講BIT之前，我們來先了解一個(gè)函數(shù)：對于任意正整數(shù)x懒熙，我們定義lowbit（x）為x的二進(jìn)制中最右邊的1所對應(yīng)的值丘损，比如，5的二進(jìn)制是101工扎，那么lowbit（5）= 1徘钥；4的二進(jìn)制是100，那么lowbit（4） = 4肢娘；在程序?qū)崿F(xiàn)中呈础，lowbit代碼如下
lowbit（x） = x&(-x)
這里用到的是按位運(yùn)算舆驶。計(jì)算機(jī)里面的整數(shù)采用補(bǔ)碼表示，-x實(shí)際上是x在二進(jìn)制中按位取反而钞，末位+1后的結(jié)果沙廉，二者按位取“與”之后，前面全部變成0臼节，之后的lowbit保持不變撬陵；
38288= 10010101100{10000}
-38288=01101010011{10000}
從這兒你可以自己算算，38288整個(gè)取反之后是01101010011{01111}网缝，再+1 就是01101010011{10000}巨税，所以這樣來說是不是容易懂些呢？接下來給大家附上一張BIT 的圖粉臊，其實(shí)也不是很難懂草添，但是我想要的圖我找不到了，所以就附一個(gè)別的圖吧扼仲，希望大家能盡量去看远寸，在下面我會(huì)給大家解釋其中C數(shù)組的含義（這是原博客中附帶的圖，我下面貼張我從書上看到的圖犀盟，我覺得更好的理解）
我的書上的圖而晒，別看我瞎寫的那些蝇狼，這個(gè)的那些黑坨坨就是C[i]下面有一個(gè)下標(biāo)索引的阅畴，看見沒？array indices那個(gè)迅耘。這個(gè)是在原來的數(shù)組A[i]上進(jìn)行的整合贱枣，
其中我們可以看到C[i]是有分層問題的，那么到底是怎么分層的呢颤专，實(shí)際上就是根據(jù)lowbit（i）的值來分的層纽哥。
在這里我們可以看到BIT是有連線的，但實(shí)際上這些連線在計(jì)算機(jī)中并不存在栖秕，只是為了讀者好理解才加上的春塌。其實(shí)BIT本身就是一棵二叉樹（具體請翻閱前面BIT的定義），那么這棵樹上面就會(huì)有父親節(jié)點(diǎn)和左右兒子節(jié)點(diǎn)（實(shí)際上在圖中沒有看到右孩子與父親節(jié)點(diǎn)的連線簇捍，我們可以想象一下）關(guān)于在BIT上節(jié)點(diǎn)的父子關(guān)系只壳，我們是這樣定義的：
對于節(jié)點(diǎn)i，如果它是左子節(jié)點(diǎn)暑塑，那么它的父節(jié)點(diǎn)的編號(hào)為i+lowbit(i)吼句；如果它是右子節(jié)點(diǎn)，那么它的父節(jié)點(diǎn)編號(hào)為i+lowbit(i)事格。大家可以自己證明一下這個(gè)東西惕艳。搞清楚BIT 結(jié)構(gòu)之后搞隐，我們來講一下這個(gè) C[] 數(shù)組是干嘛的。
C數(shù)組實(shí)際上只是個(gè)輔助數(shù)組远搪，其中C[i]=A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+……+A[i];可以看出劣纲，C數(shù)組就是用來輔助計(jì)算前綴和S[i]的威根；
那么我們有了C數(shù)組之后筑辨，如何計(jì)算S[i]呢？順著i節(jié)點(diǎn)往左走雷猪，邊走邊往上爬（這里請注意棠耕，不一定沿著BIT中的邊爬）余佛，把沿途的C[i]累加起來就好了（請讀者注意，這里沿途經(jīng)過的C[i]毫無遺漏和重復(fù)的走完了A[i]）窍荧，那么下面我給大家附上這個(gè)求前綴和操作的代碼（這里我只會(huì)給出核心代碼辉巡，因?yàn)槿看a給出真的就是沒必要）：
下面來講一下修改問題，因?yàn)锽IT是一棵樹蕊退，而且根據(jù)前面的C[i]的定義郊楣，我們可以知道，當(dāng)某個(gè)A[i]改變時(shí)瓤荔，有一些C[i]也會(huì)改變净蚤，那么需要更改那些C數(shù)組中的元素呢？從C[i]開始往右走输硝，邊走邊“往上爬”（同上今瀑，不一定要沿著圖中的邊爬），沿途修改經(jīng)過所有節(jié)點(diǎn)對應(yīng)的C[i]值即可点把。
這兩個(gè)操作的時(shí)間復(fù)雜度都是O（logn）預(yù)處理方法是將A和C數(shù)組清空橘荠，再執(zhí)行n次add操作，總時(shí)間復(fù)雜度為O（nlogn）郎逃；
整體代碼如下：
#include<iostream>
using namespace std;
int A[16]={100,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
int C[16];
// 位運(yùn)算哥童，lowbit
int lowbit(int x)
{
return x&(-x);
}
//求出在某個(gè)數(shù)之前的sum值，如果要求區(qū)間i,j這種的話褒翰，直接sum[j]-sum[i]即可
int sum(int x)
{
int ret=0;
while(x>0)
{
ret+=C[x];
x-=lowbit(x);
}
return ret;
}
//在A[]數(shù)組中加某個(gè)數(shù)贮懈，會(huì)對組成的C[]數(shù)組的二叉索引樹結(jié)構(gòu)進(jìn)行重構(gòu)，對加了相應(yīng)位置的C[]重新賦值
void add(int x,int d)
{
while(x<16)
{
C[x]+=d;
x+=lowbit(x);
}
}
int main()
{
//初始化過程优训，A[]數(shù)組是一開始給定的要處理的數(shù)組朵你，C[]數(shù)組是要構(gòu)建二叉樹的數(shù)組，利用lowbit可以在C[]各個(gè)位置之間進(jìn)行跳躍型宙，實(shí)現(xiàn)轉(zhuǎn)移效果
for (int i = 1; i < 16; ++i)
{
add(i,A[i]);
}
cout<<"* | ";
for(int i=0;i<16;++i)
cout<<sum(i)<<" | ";
cout<<"* "<<endl;
return 0;
}
下面是幾個(gè)運(yùn)行結(jié)果的展示：
int main()
{
for (int i = 1; i < 16; ++i)
{
add(i,A[i]);
}
cout<<"* | ";
for(int i=0;i<16;++i)
cout<<sum(i)<<" | ";
cout<<"* "<<endl;
cout<<sum(5)<<endl;
// 在A[5] 位置+1 撬呢，注意！注意Ｗ倍摇魂拦！A[0] 是無用的元素毛仪，加上是為了數(shù)組的計(jì)算方便直觀，索引數(shù)就等于是第幾個(gè)元素
add(5,10);
cout<<sum(5)<<endl;
return 0;
}
正文之后
溜了溜了芯勘。不知諸位能否明白我這種理解了一個(gè)數(shù)據(jù)結(jié)構(gòu)之后的喜悅箱靴？
