0. Introduction

AtCoder Official Algorithm Collection AtCoder Library (** ACL **) released on September 7, 2020 it was done. I thought it was a good opportunity because most of the algorithms and data structures recorded in ACL were new to me, so I did everything from studying algorithms to implementing them in Python.

In this article we will look at ** Fenwick_Tree ** (** Fenwick Tree **).

Target readers

If you look at the ACL code but ** don't know what you're doing **.
Those who do not understand C ++ and want to read it in Python.

Untargeted readers

Those who want Python-optimized code for ACLs. → Since it was implemented so that it would be the same as ACL as much as possible, the execution speed in Python is not considered at all. There seems to be a movement to make it available directly from Cython, so it may be good to follow that.

Referenced

About the mechanism of fenwick tree

Binary indexed tree (slide) Very easy to understand
[Wikipedia-Fenwick Tree](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%8B%E3%83%83%E3%82%AF % E6% 9C% A8)

About bit operation

1. What is Fenwick Tree?

To understand "What is Fenwick Tree?", Let us first consider the following questions.

Given a sequence of length $ N $ $ a_1, a_2, \ cdots, a_N $, many of the following two types of queries are thrown against this sequence: Please handle this.

** add **: Since $ i and x $ are given, add $ x $ to $ a_i $.
** sum **: Since $ i $ is given, the sum from the beginning to the $ i $ th is calculated.

In the following, the given value may be explicitly written as add (i, x), sum (i).

1.1. First of all, a straightforward answer

First, think as written in the problem. Query add

a_i \leftarrow a_i+x

Therefore, it can be processed with the amount of calculation $ O (1) $. On the other hand, the query sum

a_1+a_2+\cdots+a_i

Is required to be calculated, so the complexity is $ O (N) $.

1.2. Speaking of partial sum, cumulative sum

Speaking of partial sum of sequences like query sum, you can think of cumulative sum. In fact, if you prepare an array that is the cumulative sum of the sequence $ a $, the query sum can be processed with $ O (1) $. But what about the query add? If you change one part of the sequence $ a $, you need to recalculate the cumulative sum, so the amount of calculation will be $ O (N) $ in the end.

1.3. At that time, Fenwick Tree

Both the stupid answer and the cumulative sum required a computational complexity of $ O (N) $ to process both add and sum queries. Of course, it would be nice if this was enough, but I want to make it faster. .. .. ** Fenwick Tree ** appears at such times. Fenwick Tree can process both ** of queries add and sum with $ O (\ log N) $ at a time! ** ** Fenwick trees are also known as ** Binary Indexed Tree (BIT) **.

2. What kind of tree is a fenwick tree?

Let's take a look at the structure of Fenwick Tree. Therefore, let's consider the case of $ N = 7 $ as the length of the sequence $ a $.

2.1. Make a tree for the time being

Since the fenwick tree is supposed to be a tree structure, we will make a tree from the sequence $ a $. Specifically, as shown in the figure below, a tree is created with each term in the sequence as a leaf and the sum of the two terms as the parent.

Now that we have a tree (forest?), Let's use this tree to solve the problems in the previous chapter. First is the query add. As an example, consider updating $ a_3 $. There are three places where $ a_3 $ is related, so you can update these. More generally, there are as many places to update as the height of a tree. The height of this tree is approximately $ \ log N $, so the amount of calculation is $ O (\ log N) $. How about the query sum? For example, when finding the sum up to the 7th

\sum_{i=1}^{7}{a_i}=(a_1+a_2+a_3+a_4)+(a_5+a_6)+(a_7)

So you should look at 3 places. In general, you only need to look at the height of the tree, so the amount of calculation is $ O (\ log N) $.

2.2. Smarter

So it seems that $ O (\ log N) $ can be used for both add and sum queries. I'd like to say that I'm happy, but the tree I made earlier is actually wasteful. Actually, there are some places that I have never seen when I check all the sums up to the first, the sum up to the second, $ \ cdots $, and the sum up to the seventh. After removing them, it will look like the figure below. It contains all the information needed to process the query sum. (The query add only updates the relevant location, so that's okay.)

2.3. The true appearance of fenwick trees

So far, we have shown the tree structure to know "what kind of tree is a fenwick tree?", But if you look at the code of the fenwick tree in ACL, it is a one-dimensional object with a length of $ N $ of data. There is only an array. Where is the tree? Actually, this data is packed with a tree structure. Specifically, ** I have information on "directions to follow" using the index of the array **. Now, let's change the tree we saw above into a one-dimensional array. As you may have noticed, by removing the unnecessary part earlier, the remaining place is just $ N $. And the maximum value of the index to take the integration by parts (red underlined part in the figure below) is different in each place. You can use this value to create data.

So, I found that the reality of Fenwick Tree (in terms of implementation) is a one-dimensional array ** packed with integration by parts in a nice way.

3. How to walk in a strange array

Our purpose is to handle queries add, sum using this strange array data. In this chapter we will look at how each query gives you "** directions to follow **".

3.1. Query add

First is the query add. The query add (i, x) can go anywhere that contains $ a_i $. Let's look at some examples.

Index to update	Directions to follow
1	1 → 2 → 4
2	2 → 4
5	5 → 6

It's hard to see the law with just this. However, if you pay attention to the "difference between the current index and the next index", the outlook will improve at once.

The red letters are the indexes of data, the green arrows are the directions, and the green letters are the index differences. Looking at this figure, you can see that you can add +1 from the bottom and +2 from the middle. The upper, middle, and lower parts of this figure are divided by "the number of terms to be summed", and this is called "** length **". For example, "the length ofdata [6]" is 2. Then, in order to process the query add (i, x), we can say that:

Index

i^\prime = i + (data[i]Length of)

And add x to data [i].

3.2. Query sum

Next, let's look at the query sum. The query sum (i) should be traced to cover $ a_1, \ cdots, a_i $ and summed up. As with the query add earlier, let's pay attention to the "difference between the current index and the next index".

After all, by using "length", you can find the next index. Therefore, in order to process the query sum (i), we can say that:

Index

i^\prime = i - (data[i]Length of)

While updating, take the sum of each data [i].

3.3. Length

It turns out that both queries can be processed as long as "the length ofdata [i]" is obtained. So how do you get the length of data [i] from i? Recall that fenwick trees are also known as Binary Indexed Trees. Shows the index and its binary display for each length.

From this table, the length corresponds to "** the index is displayed in binary and the place where '1' appears for the first time when viewed from the right ", that is, " the least significant bit of '1' **". You can see that. The least significant bit is often written in English as ** Least Significant Bit (LSB) **. And "LSB of '1' in i" (written as = LSB (i)) can be easily obtained by ** bit operation **.

LSB(i) \quad=\quad i\quad\&\quad(-i)

Where & is a bitwise AND operation. Bitwise operations for negative numbers are expressed in 2's complement It is treated as represented by (Reference). Let's look at some examples. Here, we will consider the 8-bit two's complement representation. When $ i = 6 $

\begin{aligned}
LSB(6) &= 6 \quad\&\quad(-6)\\
&= (00000110)_2 \quad\&\quad (11111010)_2\\
&= (00000010)_2\\
&= 2
\end{aligned}

When $ i = 7 $

\begin{aligned}
LSB(7) &= 7 \quad\&\quad(-7)\\
&= (00000111)_2 \quad\&\quad (11111001)_2\\
&= (00000001)_2\\
&= 1
\end{aligned}

When $ i = 24 $

\begin{aligned}
LSB(24) &= 24 \quad\&\quad(-24)\\
&= (00011000)_2 \quad\&\quad (11101000)_2\\
&= (00001000)_2\\
&= 8
\end{aligned}

Now that you're ready to implement Fenwick Tree, let's implement it.

4. Implementation

Let's implement it. Variable names, method names, etc. should be implemented according to ACL as much as possible.

4.1. Constructor

Create a class Fenwick_Tree to implement the constructor.

class Fenwick_Tree:
    def __init__(self, n):
        self._n = n  #Element count
        self.data = [0] * n

Keep the number of elements in the instance variable _n and create a list data of length n. At the time of initialization, everything is 0. This corresponds to the sequence $ a = \ {0, \ cdots, 0 \} $. If you want to initialize with a non-zero sequence, execute $ add (i, a_i) $ for each i.

Caution Until the previous chapter, data was ** 1-indexed **, but in implementation it is ** 0-indexed **. Note that the Fenwick tree mechanism is 1-indexed, so you will need to shift it by 1 when accessing data.

4.2. add Let's implement it from the method add first. This method corresponds to the query add (p, x).

def add(self, p, x):
    assert 0 <= p < self._n
    p += 1  # 0-indexed -> 1-indexed
    while p <= self._n:
        self.data[p - 1] += x　 #update data
        p += p & -p  #LSB to p(p)Add

As we saw in Chapter 3.1, query add finds the next index to look at by adding the LSB. Repeat this index update and data update until the array is no longer referenced.

4.3. sum Next is the method sum. In ACL, the one corresponding to query sum (i) is implemented as an internal (private) function, and the external (public) function actually used is a more general one. It is implemented. Specifically, by specifying two values l and r, the integration by parts of the left-closed and right-open half-open interval [l, r)

\sum_{i = l}^{r - 1}{a_i}

Returns. (a is 0-indexed) First, implement from the internal function corresponding to the query sum. This returns the integration by parts $ a_0 + \ cdots + a_ {r --1} $ of the half-open interval [0, r) for r. However, it returns 0 when $ r = 0 $. I also added an underscore (_) at the beginning to indicate that it is an internal function.

def _sum(self, r):
    s = 0  #Variable to put the sum
    while r > 0:
        s += self.data[r - 1]
        r -= r & -r  #r to LSB(r)Subtract
    return s

As we saw in Chapter 3.2, the query sum knows which index to look at next by subtracting the LSB. While updating this, take the sum of each data [r]. Use this internal function to implement the generic external function mentioned above.

def sum(self, l, r):
    assert 0 <= l <= r <= self._n
    return self._sum(r) - self._sum(l)

([l, r)Partial sum of) = (r -Integration by parts up to 1) - (l -Integration by parts up to 1)

is.

4.4. Summary

`fenwicktree.py`


class Fenwick_Tree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n
    
    def add(self, p, x):
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    
    def sum(self, l, r):
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)
    
    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

5. Usage example

It is not necessary originally, but we are adding directly to a to see the sequence a itself.

    n = 8 
    a = [0, 1, 2, 3, 4, 5, 6, 7]
    fw = Fenwick_Tree(n)
    for i, a_i in enumerate(a): fw.add(i, a_i)  #Initialize with sequence a
    print(fw.sum(2, 4))  # 5
    print(fw.sum(6, 7))  # 6 sum(i, i + 1)In a[i]Can be obtained
    fw.add(2, 6)  # a[2] += 6
    a[2] += 6
    fw.add(5, -1)  # a[5] += -1
    a[5] += -1
    print(a)  # [0, 1, 8, 3, 4, 4, 6, 7]
    print(fw.sum(0, 3))  # 9
    print(fw.sum(3, 7))  # 17

6. Problem example

AtCoder Library Practice Contest B "Fenwick Tree"

7. Conclusion

From elucidating the mechanism of Fenwick Tree to implementation in Python. Fenwick tree seems to have various applications, so I would like to study it someday.

Please let us know if you have any mistakes, bugs, or advice.

[Fenwick_Tree] AtCoder Library-Reading with Green Coder-Implementation in Python-