Tree Array Notes

Original link:

I have learned the line segment tree for a long time, but I am ashamed that the simpler tree-like array has not been deeply understood, and it only stays at the level of memorizing the code. Learn about tree arrays seriously today.


Tree arrays (Binary Index Tree, BIT / Fenwick Tree) support two simple operations, single-point modification and interval query , and the time complexity is $O(\log n)$. Its implementation is simpler and faster than segment trees, but slightly less powerful.



We use $C_i$ to represent a section of the $A$ array, define the binary representation of $x$, the position of the lowest $1$ is $\operatorname{lowbit}(x)$, then use $C_i$ to represent $ The subscript range $[i-\operatorname{lowbit}(i)+1, i]$ of the A$ array. For example, $4_{(10)} = 100_{(2)}$, $100_{(2)}-\operatorname{lowbit}(100_{(2)})+1_{(2)}=1_ {(2)}=1_{(10)}$, then the interval represented by $C_4$ is $[1, 4]$. Through this design, the tree-like array compresses the number of nodes to the same length as the array, unlike the line segment tree that requires $2n$ nodes.

The reason for this feature is that for the position $i$, the height of the corresponding node is the number of bits of $\operatorname{lowbit}(i)$. The first-level nodes are all $2^0 + 2^1k$, that is, all numbers of $\operatorname{lowbit}(i)=1$; the second-level nodes are all $2^1 + 2^2k$, that is All numbers of $\operatorname{lowbit}(i)=2$; the third level node is all $2^2 + 2^3k$ , that is, all numbers of $\operatorname{lowbit}(i)=4$; And so on. That is to say, for the position $i$, trace vertically upwards at this position, and the number of layers that can be traced is the number of $0$ at the end of the binary representation of $i$. The height of the node determines the size of its subtree, so the size of the information interval it represents must be $2^{the number of 0s at the end of i}=\operatorname{lowbit}(i)$.

*From Reference 1


How is $\operatorname{lowbit}$ calculated? We have this formula: $\operatorname{lowbit}(x)=(x)&(-x)$. In computers, signed numbers are represented in two’s complement. In two’s complement notation, the opposite of $x$ -x = ~x + 1 , that is, the bitwise negation plus one. For example, the location of the last $1$ of $x$ is $\cdots 01000\cdots$, after the bitwise negation is $\cdots 10111\cdots$, and it is added again and again to become $\cdots 11000\cdots$; The bits are the opposite of the original. At this point, we do bitwise AND with $x$, and the result is $01000\cdots$, which is $\operatorname{lowbit}(x)$.

single point modification

The modification operation is similar to the process of climbing up a tree. For example, if we want to modify the third element, then we need to modify $C_3, C_4, C_8$ in turn, which is $11, 100, 1000$ in binary, and find that the subscript $x$ needs $x += \operatorname{lowbit every time }(x)$ until the top is reached.

 1 2 3 4 5 6 
 int add ( int x , int y ) { while ( x <= n ) { tree [ x ] += y ; x += lowbit ( x ); } }

Interval query (prefix sum)

For example, query the prefix sum of the sixth element, that is, the interval $[1, 6]$. First, the interval represented by $C_6$ is $[5, 6]$, and then jump to $C_4$, which represents the interval $[1, 4]$, and it is OK to add up. How did you jump from $C_6$ to $C_4$? It’s actually $110 – \operatorname{lowbit}(110) = 100$. So the subscript $x$ requires $x -= \operatorname{lowbit}(x)$ every time until $x<1$.

 1 2 3 4 5 6 7 8 
 int query ( int x ) { int sum = 0 ; while ( x ) { sum += tree [ x ]; x -= lowbit ( x ); } return sum ; }

As for the sum of the interval $[a, b]$, you only need to find $[1, b]$ and $[1, a)$ respectively and then subtract them.

$O(n)$ build tree

The brute force method is to make $n$ single-point modifications, and the time complexity is $O(n\log n)$.

There are two ways to achieve $O(n)$ tree building.

prefix sum

As mentioned earlier, the interval represented by $C_i$ is $[i-\operatorname{lowbit}(i)+1, i]$, then we can preprocess a $sum$ prefix and array first, and then calculate the $C$ array.

 1 2 3 4 5 
 void init () { for ( int i = 1 ; i <= n ; ++ i ) { C [ i ] = sum [ i ] - sum [ i - lowbit ( i )]; } }

Contribute backwards

We can easily know that the father of the current point $i$ is $i+\operatorname{lowbit}(i)$, so update the father with its own value.

 1 2 3 4 5 6 7 
 void init () { for ( int i = 1 ; i <= n ; ++ i ) { C [ i ] += a [ i ]; int j = i + lowbit ( i ); if ( j <= n ) C [ j ] += C [ i ]; } }


  1. What is the principle of tree array? – SleepyBag’s answer – Knowing
  2. Algorithm Study Notes (2): Tree Array – Pecco’s Article – Knowing

This article is reproduced from:
This site is for inclusion only, and the copyright belongs to the original author.

Leave a Comment