回憶一下lowbit(x)指的就是二進位制形式下

從低位開始出現的第一個1的位置。

1。查詢的部分很容易理解，就是將x不斷從低位到高位依次將1位變成0位的過程

2。現在來考慮更新部分，首先考慮y>x在二進位制上的表現就是從高位開始，y與x首次出現不同的位置上y是1而x是0，即y和x分別為

X表示兩者在該位置上的數字相同，而？表示該位置上的數字未知，在已知x要尋找到滿足條件的y，則y需要滿足以下條件y>x>(y-lowbit(y))，一般化的考慮y和x的形式

再次回憶y-lowbit(y)的意思就是將低位的第一個1變成0，顯然y的低位1在變成0之後還是比x要大，除非低位1與高位1在同一個位置，即

所以我們要找的y是符合這樣的條件的，找到x中任意的一個高位0，將此高位以上的位置維持不變，將此位置0變成1，然後這一位置之後的低位都變成0，那麼具體如何由x得到這樣的y呢，考慮x是這樣的形式

依次類推，注意到透過這種方法我們在原來x的基礎上，由低位向高位推進，依次將遇到的0為變成1位，並將此以後的低位保持為0，此位之前的高位保持不變，符合前述的需要的y的條件。

這樣我們就得到了樹狀陣列的更新演算法。