Updated on 

Fenwick木（BIT）

Fewnick Tree

BinaryIndexedTree(BIT) とも呼ばれるデータ構造です。要素の更新と区間の和を行うクエリを高速に処理できます。

BITの実装

構造

1
2
3
4
5
6
|---------------------------------------|
|-------------------|                   |
|---------|         |---------|         |
|----|    |----|    |----|    |----|    |
|  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |
|0001|0010|0011|0100|0101|0110|0111|1000|

区間和を求める

0 になるまでLSBを減算しながら足す

例)

  • 配列
  • クエリ: 
1
2
3
4
|               37              |
|       24      |               |
|   8   |       |   10  |       |
| 5 |(3)| 7 |(9)| 6 |(4)| 1 |(2)|
i 2進表示 合計
7 0111 1 (0 + 1)
6 0110 11 (1 + 10)
4 0100 35 (11 + 24)
0 0000 35

要素の更新

に を足す

にLSBを加算しながら更新

例)

  • 配列
  • クエリ: に を足す
i 2進表示
5 0101
6 0110
8 1000 
1
2
3
4
|           37 → 39             |
|       24      |               |
|   8   |       | 10→12 |       |
| 5 |(3)| 7 |(9)|6→8|(4)| 1 |(2)|

最下位ビット

(LSB; Least Significant Bit)とも言う

2進数で表したとき、もっとも小さい位をあらわすbit

  • のLSBは2

求め方

2の補数表現を利用すると、

1
-i <- ~i + 1

と表される。(~はbit反転)

このとき、最下位ビットは

1
i & -i

として求められる。

BIT.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# BIT
class BIT:
    def __init__(self, n):
        self.size = n
        self.arr = [0] * (n + 1)
    
    def sum(self, i):
        s = 0
        while i:
            s += self.arr[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        while i <= self.size:
            self.arr[i] += x
            i += i & -i


# ----- query -----
bit = BIT(8)

bit.add(1, 5)
bit.add(2, 3)
bit.add(3, 7)
bit.add(4, 9)
bit.add(5, 6)
bit.add(6, 4)
bit.add(7, 1)
bit.add(8, 2)

print(bit.arr)

print(bit.sum(7))

bit.add(5, 2)

print(bit.sum(8))

##### OUT #####
5
20
0
[0, 5, 8, 7, 24, 6, 10, 1, 37]
35
39

区間の和を求める

  • 累積和みたいに処理
BIT.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# BIT
class BIT:
    def __init__(self, n):
        self.size = n
        self.arr = [0] * (n + 1)
    
    def sum_1(self, i):
        s = 0
        while i:
            s += self.arr[i]
            i -= i & -i
        return s
    
    def sum(self, i, j):
        """[i, j) の和を求める"""
        return self.sum_1(j-1) - self.sum_1(i-1)
    
    def add(self, i, x):
        while i <= self.size:
            self.arr[i] += x
            i += i & -i

# ----- query -----
bit = BIT(8)

bit.add(1, 5)
bit.add(2, 3)
bit.add(3, 7)
bit.add(4, 9)
bit.add(5, 6)
bit.add(6, 4)
bit.add(7, 1)
bit.add(8, 2)

print(bit.sum(1, 2))
print(bit.sum(4, 8))
print(bit.sum(1, 1))

##### OUT #####
5
20
0

参考

このページはHexoとStellarを使用して作成されました。