Fenwick Tree in 5 minutes↵
==================↵
↵
Fenwick tree is a dynamic prefix sums array. You can:↵
↵
- Add values to elements in $O(\log N)$↵
- Get prefix sum in $O(\log N)$↵
↵
Structure↵
------------------↵
↵
Fenwick tree is a single array. Each element $i$ has sum of elements on some range. Each range ends in its element, but they have different sizes.↵
↵
Here's how the segments look for each element:↵
↵
↵
↵
See a pattern? Sizes of ranges go like $1, 2, 1, 4, 1, 2, 1, 8, \dots$↵
↵
How do we get size of range for element $i$?↵
↵
<spoiler summary="Answer">↵
Look at binary representation of index $i$:↵
↵
$${11}_{10} = {1011}_2$$↵
↵
We can count the number of consecutive ones on the right side (least significant bits). Say this number is $k$. Then the size of the range is $2^k$.↵
</spoiler>↵
↵
So each element in fenwick array will keep the sum of its segment. Initially the array is filled with zeroes.↵
↵
Adding Values↵
------------------↵
↵
What happens when you add $x$ to element at position $i$? You need to increment ${tre}[i]$ by $x$. But also, you need to update other ranges that contain this position. How do we find them?↵
↵
↵
↵
<spoiler summary="Answer">↵
Look at binary representation of $i$ again. What is the next index, where the range contains this element? Its the same index, but with the first $0$ from the right (least significant) replaced with a $1$:↵
↵
↵
$$1011\mathbf{0}111 \rightarrow 1011\mathbf{1}111$$↵
</spoiler>↵
↵
To find such index we'll use some binary magic. Try to figure this out for yourself.↵
↵
<spoiler summary="Answer">↵
What happens when you add $1$ to your index $i$ in binary? All consecutive ones turn into zeroes and the first zero becomes a one:↵
↵
↵
$$1011\mathbf{0111} + 1 = 1011\mathbf{1000}$$↵
↵
So if we take bitwise OR of the two, we'll get the desired index.↵
↵
~~~~~↵
inline void add(int i, int x)↵
{↵
for(; i < MAXN; i |= (i+1)) ↵
{↵
tre[i] += x;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
Getting Prefix Sum↵
------------------↵
↵
To get prefix sum of first $i$ elements, we'll start at position $i-1$. We'll take the sum on the range for that index, and jump to the next index. ↵
↵
↵
↵
To do that, we simply subtract the range size. But, there is a cleaner solution, using bitwise magic again.↵
↵
<spoiler summary="Answer">↵
Look at binary. If length of the consecutive segment of ones is $k$, what does subtracting $2^k$ look like? The segment of ones itself has value $1 + 2 + \dots = 2^k-1$. So we can turn all those ones into zeroes, and then simply subtract a one.↵
↵
How do we remove the segment of ones? Same way we did before. We'll take $i$ and $i+1$, but instead of ORing them, we will AND them.↵
↵
~~~~~↵
int sum(int r)↵
{↵
r--;↵
int res = 0;↵
for(; r >= 0; r = (r & (r+1))-1)↵
{↵
res += tre[r];↵
}↵
return res;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
Time Complexity↵
------------------↵
↵
As i said at the start, time complexity for both operations is $O(\log N)$. Why?↵
↵
- For addition, every iteration turns one bit into a one. So number of iterations is at most number of bits, which is $O(\log N)$.↵
- For sum, every iteration increases the size of the segment of ones. So number of iterations is also at most number of bits. $O(\log N)$↵
↵
Full Code↵
------------------↵
↵
~~~~~↵
const int MAXN = 200005;↵
↵
struct fenwick↵
{↵
int tre[MAXN];↵
↵
fenwick() {}↵
↵
inline void clear(int n)↵
{↵
for(int i = 0; i < n; i++)↵
{↵
tre[i] = 0;↵
}↵
}↵
↵
inline void add(int i, int x)↵
{↵
for(; i < MAXN; i |= (i+1))↵
{↵
tre[i] += x;↵
}↵
}↵
↵
inline int sum(int r)↵
{↵
r--;↵
int res = 0;↵
for(; r >= 0; r = (r & (r+1))-1)↵
{↵
res += tre[r];↵
}↵
return res;↵
}↵
};↵
~~~~~↵
↵
Conclusion↵
------------------↵
↵
Fenwick tree is used to keep a dynamic prefix sums array with every operation being $O(\log N)$.↵
↵
<spoiler summary="Can it be used for other prefix values, like minimum or maximum?">↵
Yes, but you can't really **set** individual values, you can only update them (i.e. min= or max= )↵
</spoiler>↵
↵
<spoiler summary="What about segment trees?">↵
Segment trees are far more versatile, but the implementation for fenwick tree is much simpler and faster.↵
</spoiler>↵
↵
<spoiler summary="Can i get a Bolba?">↵
Sure you can:↵
↵
↵
↵
</spoiler>↵
↵
==================↵
↵
Fenwick tree is a dynamic prefix sums array. You can:↵
↵
- Add values to elements in $O(\log N)$↵
- Get prefix sum in $O(\log N)$↵
↵
Structure↵
------------------↵
↵
Fenwick tree is a single array. Each element $i$ has sum of elements on some range. Each range ends in its element, but they have different sizes.↵
↵
Here's how the segments look for each element:↵
↵
↵
↵
See a pattern? Sizes of ranges go like $1, 2, 1, 4, 1, 2, 1, 8, \dots$↵
↵
How do we get size of range for element $i$?↵
↵
<spoiler summary="Answer">↵
Look at binary representation of index $i$:↵
↵
$${11}_{10} = {1011}_2$$↵
↵
We can count the number of consecutive ones on the right side (least significant bits). Say this number is $k$. Then the size of the range is $2^k$.↵
</spoiler>↵
↵
So each element in fenwick array will keep the sum of its segment. Initially the array is filled with zeroes.↵
↵
Adding Values↵
------------------↵
↵
What happens when you add $x$ to element at position $i$? You need to increment ${tre}[i]$ by $x$. But also, you need to update other ranges that contain this position. How do we find them?↵
↵
↵
↵
<spoiler summary="Answer">↵
Look at binary representation of $i$ again. What is the next index, where the range contains this element? Its the same index, but with the first $0$ from the right (least significant) replaced with a $1$:↵
↵
↵
$$1011\mathbf{0}111 \rightarrow 1011\mathbf{1}111$$↵
</spoiler>↵
↵
To find such index we'll use some binary magic. Try to figure this out for yourself.↵
↵
<spoiler summary="Answer">↵
What happens when you add $1$ to your index $i$ in binary? All consecutive ones turn into zeroes and the first zero becomes a one:↵
↵
↵
$$1011\mathbf{0111} + 1 = 1011\mathbf{1000}$$↵
↵
So if we take bitwise OR of the two, we'll get the desired index.↵
↵
~~~~~↵
inline void add(int i, int x)↵
{↵
for(; i < MAXN; i |= (i+1)) ↵
{↵
tre[i] += x;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
Getting Prefix Sum↵
------------------↵
↵
To get prefix sum of first $i$ elements, we'll start at position $i-1$. We'll take the sum on the range for that index, and jump to the next index.
↵
↵
↵
To do that, we simply subtract the range size. But, there is a cleaner solution, using bitwise magic again.↵
↵
<spoiler summary="Answer">↵
Look at binary. If length of the consecutive segment of ones is $k$, what does subtracting $2^k$ look like? The segment of ones itself has value $1 + 2 + \dots = 2^k-1$. So we can turn all those ones into zeroes, and then simply subtract a one.↵
↵
How do we remove the segment of ones? Same way we did before. We'll take $i$ and $i+1$, but instead of ORing them, we will AND them.↵
↵
~~~~~↵
int sum(int r)↵
{↵
r--;↵
int res = 0;↵
for(; r >= 0; r = (r & (r+1))-1)↵
{↵
res += tre[r];↵
}↵
return res;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
Time Complexity↵
------------------↵
↵
As i said at the start, time complexity for both operations is $O(\log N)$. Why?↵
↵
- For addition, every iteration turns one bit into a one. So number of iterations is at most number of bits, which is $O(\log N)$.↵
- For sum, every iteration increases the size of the segment of ones. So number of iterations is also at most number of bits. $O(\log N)$↵
↵
Full Code↵
------------------↵
↵
~~~~~↵
const int MAXN = 200005;↵
↵
struct fenwick↵
{↵
int tre[MAXN];↵
↵
fenwick() {}↵
↵
inline void clear(int n)↵
{↵
for(int i = 0; i < n; i++)↵
{↵
tre[i] = 0;↵
}↵
}↵
↵
inline void add(int i, int x)↵
{↵
for(; i < MAXN; i |= (i+1))↵
{↵
tre[i] += x;↵
}↵
}↵
↵
inline int sum(int r)↵
{↵
r--;↵
int res = 0;↵
for(; r >= 0; r = (r & (r+1))-1)↵
{↵
res += tre[r];↵
}↵
return res;↵
}↵
};↵
~~~~~↵
↵
Conclusion↵
------------------↵
↵
Fenwick tree is used to keep a dynamic prefix sums array with every operation being $O(\log N)$.↵
↵
<spoiler summary="Can it be used for other prefix values, like minimum or maximum?">↵
Yes, but you can't really **set** individual values, you can only update them (i.e. min= or max= )↵
</spoiler>↵
↵
<spoiler summary="What about segment trees?">↵
Segment trees are far more versatile, but the implementation for fenwick tree is much simpler and faster.↵
</spoiler>↵
↵
<spoiler summary="Can i get a Bolba?">↵
Sure you can:↵
↵
↵
↵
</spoiler>↵
↵
