ํ์ ํธ๋ฆฌ (Fenwick Tree / Binary Indexed Tree)
ํ์ ํธ๋ฆฌ (Fenwick Tree / Binary Indexed Tree)¶
๊ฐ์¶
ํ์ ํธ๋ฆฌ(BIT: Binary Indexed Tree)๋ ๊ตฌ๊ฐ ํฉ ์ฟผ๋ฆฌ์ ์ ์ ๋ฐ์ดํธ๋ฅผ O(log n)์ ์ฒ๋ฆฌํ๋ ์๋ฃ๊ตฌ์กฐ์ ๋๋ค. ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ๋ณด๋ค ๊ตฌํ์ด ๊ฐ๋จํ๊ณ ๋ฉ๋ชจ๋ฆฌ ํจ์จ์ ์ ๋๋ค.
๋ชฉ์ฐจ¶
1. ํ์ ํธ๋ฆฌ ๊ฐ๋ ¶
1.1 ๊ตฌ์กฐ¶
ํ์
ํธ๋ฆฌ: 1-indexed ๋ฐฐ์ด ๊ธฐ๋ฐ
ํต์ฌ ์์ด๋์ด: i๋ฒ์งธ ์์๊ฐ ๋ด๋นํ๋ ๊ตฌ๊ฐ์
i์ ์ตํ์ ๋นํธ(lowbit)์ ์ํด ๊ฒฐ์
lowbit(i) = i & (-i)
์์ (n=8):
์ธ๋ฑ์ค: 1 2 3 4 5 6 7 8
lowbit: 1 2 1 4 1 2 1 8
๋ด๋น๊ตฌ๊ฐ: [1,1][1,2][3,3][1,4][5,5][5,6][7,7][1,8]
tree[1] = arr[1]
tree[2] = arr[1] + arr[2]
tree[3] = arr[3]
tree[4] = arr[1] + arr[2] + arr[3] + arr[4]
tree[5] = arr[5]
tree[6] = arr[5] + arr[6]
tree[7] = arr[7]
tree[8] = arr[1] + ... + arr[8]
1.2 lowbit ์๊ฐํ¶
์ธ๋ฑ์ค๋ฅผ ์ด์ง์๋ก ํํํ์ ๋:
1 = 0001 โ lowbit = 1 โ tree[1] = A[1]
2 = 0010 โ lowbit = 2 โ tree[2] = A[1..2]
3 = 0011 โ lowbit = 1 โ tree[3] = A[3]
4 = 0100 โ lowbit = 4 โ tree[4] = A[1..4]
5 = 0101 โ lowbit = 1 โ tree[5] = A[5]
6 = 0110 โ lowbit = 2 โ tree[6] = A[5..6]
7 = 0111 โ lowbit = 1 โ tree[7] = A[7]
8 = 1000 โ lowbit = 8 โ tree[8] = A[1..8]
ํจํด:
- ํ์ ์ธ๋ฑ์ค: lowbit = 1 (์๊ธฐ ์์ ๋ง)
- 2์ ๊ฑฐ๋ญ์ ๊ณฑ: lowbit = ์ธ๋ฑ์ค (1๋ถํฐ ์์ ๊น์ง)
1.3 ์๊ฐ/๊ณต๊ฐ ๋ณต์ก๋¶
โโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโ
โ ์ฐ์ฐ โ ์๊ฐ โ ์ค๋ช
โ
โโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโผโโโโโโโโโโโโโโค
โ ๊ตฌ์ฑ โ O(n) โ ๋๋ O(nlogn)โ
โ ์ ์
๋ฐ์ดํธ โ O(log n) โ ๊ฐ ๋ณ๊ฒฝ โ
โ ํ๋ฆฌํฝ์ค ํฉ โ O(log n) โ [1, i] ํฉ โ
โ ๊ตฌ๊ฐ ํฉ โ O(log n) โ [l, r] ํฉ โ
โโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโดโโโโโโโโโโโโโโ
๊ณต๊ฐ: O(n) - ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ์ 1/2~1/4
2. ๊ธฐ๋ณธ ๊ตฌํ¶
2.1 Python ๊ตฌํ¶
class FenwickTree:
def __init__(self, n):
"""ํฌ๊ธฐ n์ ํ์
ํธ๋ฆฌ (1-indexed)"""
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta):
"""arr[i] += delta"""
while i <= self.n:
self.tree[i] += delta
i += i & (-i) # ๋ค์ ๋
ธ๋๋ก ์ด๋
def prefix_sum(self, i):
"""arr[1] + arr[2] + ... + arr[i]"""
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i) # ์ด์ ๋
ธ๋๋ก ์ด๋
return total
def range_sum(self, l, r):
"""arr[l] + arr[l+1] + ... + arr[r]"""
return self.prefix_sum(r) - self.prefix_sum(l - 1)
# ์ฌ์ฉ ์์
n = 8
bit = FenwickTree(n)
# ๋ฐฐ์ด [0, 1, 2, 3, 4, 5, 6, 7, 8] ๊ตฌ์ฑ (1-indexed)
for i in range(1, n + 1):
bit.update(i, i)
print(bit.prefix_sum(4)) # 10 (1+2+3+4)
print(bit.range_sum(2, 5)) # 14 (2+3+4+5)
bit.update(3, 5) # arr[3] += 5
print(bit.range_sum(2, 5)) # 19 (2+8+4+5)
2.2 ๋ฐฐ์ด๋ก ์ด๊ธฐํ¶
class FenwickTreeFromArray:
def __init__(self, arr):
"""๋ฐฐ์ด๋ก ํ์
ํธ๋ฆฌ ๊ตฌ์ฑ - O(n)"""
self.n = len(arr)
self.tree = [0] * (self.n + 1)
# O(n) ์ด๊ธฐํ
for i in range(1, self.n + 1):
self.tree[i] += arr[i - 1] # arr์ 0-indexed
j = i + (i & (-i))
if j <= self.n:
self.tree[j] += self.tree[i]
def update(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def prefix_sum(self, i):
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i)
return total
def range_sum(self, l, r):
return self.prefix_sum(r) - self.prefix_sum(l - 1)
# ์ฌ์ฉ ์์
arr = [1, 2, 3, 4, 5, 6, 7, 8]
bit = FenwickTreeFromArray(arr)
print(bit.range_sum(1, 4)) # 10
2.3 C++ ๊ตฌํ¶
#include <vector>
using namespace std;
class FenwickTree {
private:
vector<long long> tree;
int n;
public:
FenwickTree(int n) : n(n), tree(n + 1, 0) {}
FenwickTree(const vector<int>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
for (int i = 1; i <= n; i++) {
tree[i] += arr[i - 1];
int j = i + (i & (-i));
if (j <= n) tree[j] += tree[i];
}
}
void update(int i, long long delta) {
while (i <= n) {
tree[i] += delta;
i += i & (-i);
}
}
long long prefixSum(int i) {
long long total = 0;
while (i > 0) {
total += tree[i];
i -= i & (-i);
}
return total;
}
long long rangeSum(int l, int r) {
return prefixSum(r) - prefixSum(l - 1);
}
};
3. ์ฐ์ฐ¶
3.1 ์ ๋ฐ์ดํธ ๊ณผ์ ์๊ฐํ¶
update(3, 5): arr[3] += 5
์ธ๋ฑ์ค ์ด๋: 3 โ 4 โ 8 (โ 16 ์ด๊ณผ)
3 = 0011 โ tree[3] += 5
0011 + 0001 = 0100
4 = 0100 โ tree[4] += 5
0100 + 0100 = 1000
8 = 1000 โ tree[8] += 5
1000 + 1000 = 10000 (> n, ์ข
๋ฃ)
์ํฅ๋ฐ๋ ๋
ธ๋: tree[3], tree[4], tree[8]
3.2 ์ฟผ๋ฆฌ ๊ณผ์ ์๊ฐํ¶
prefix_sum(7): arr[1] + ... + arr[7]
์ธ๋ฑ์ค ์ด๋: 7 โ 6 โ 4 โ 0
7 = 0111 โ total += tree[7] (arr[7])
0111 - 0001 = 0110
6 = 0110 โ total += tree[6] (arr[5..6])
0110 - 0010 = 0100
4 = 0100 โ total += tree[4] (arr[1..4])
0100 - 0100 = 0000
0 = 0000 (์ข
๋ฃ)
๊ฒฐ๊ณผ: tree[7] + tree[6] + tree[4] = arr[1..7]
3.3 ์ ์ฟผ๋ฆฌ (Point Query)¶
class FenwickTreePointQuery:
"""๊ตฌ๊ฐ ์
๋ฐ์ดํธ + ์ ์ฟผ๋ฆฌ"""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def range_update(self, l, r, delta):
"""arr[l..r] += delta"""
self._update(l, delta)
if r + 1 <= self.n:
self._update(r + 1, -delta)
def _update(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def point_query(self, i):
"""arr[i] ๊ฐ"""
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i)
return total
# ์์
bit = FenwickTreePointQuery(8)
bit.range_update(2, 5, 3) # arr[2..5] += 3
print(bit.point_query(3)) # 3
print(bit.point_query(6)) # 0
3.4 k๋ฒ์งธ ์์ ์ฐพ๊ธฐ¶
def find_kth(bit, k):
"""
ํ๋ฆฌํฝ์ค ํฉ์ด k ์ด์์ธ ์ต์ ์ธ๋ฑ์ค ์ฐพ๊ธฐ
(bit[i] = 1 if ์์ ์กด์ฌ)
์๊ฐ: O(log n)
"""
n = bit.n
pos = 0
total = 0
# ์ต์์ ๋นํธ๋ถํฐ ํ์
log_n = n.bit_length()
for i in range(log_n - 1, -1, -1):
next_pos = pos + (1 << i)
if next_pos <= n and total + bit.tree[next_pos] < k:
total += bit.tree[next_pos]
pos = next_pos
return pos + 1 # k๋ฒ์งธ ์์์ ์ธ๋ฑ์ค
# ์์: ๋์ k๋ฒ์งธ ์์
class DynamicKth:
def __init__(self, max_val):
self.bit = FenwickTree(max_val)
def add(self, x):
"""์์ x ์ถ๊ฐ"""
self.bit.update(x, 1)
def remove(self, x):
"""์์ x ์ ๊ฑฐ"""
self.bit.update(x, -1)
def kth(self, k):
"""k๋ฒ์งธ๋ก ์์ ์์"""
return find_kth(self.bit, k)
def count_less(self, x):
"""x๋ณด๋ค ์์ ์์ ๊ฐ์"""
return self.bit.prefix_sum(x - 1)
# ์ฌ์ฉ
dk = DynamicKth(100)
dk.add(5)
dk.add(10)
dk.add(3)
dk.add(7)
print(dk.kth(2)) # 5 (์ ๋ ฌ: 3, 5, 7, 10)
print(dk.count_less(7)) # 2 (3, 5)
4. ์์ฉ¶
4.1 ์ญ์ ์ ๊ฐ์ (Inversion Count)¶
def count_inversions(arr):
"""
์ญ์ ์: i < j์ด๊ณ arr[i] > arr[j]์ธ (i, j) ๊ฐ์
์๊ฐ: O(n log n)
"""
# ์ขํ ์์ถ
sorted_arr = sorted(set(arr))
rank = {v: i + 1 for i, v in enumerate(sorted_arr)}
max_rank = len(sorted_arr)
bit = FenwickTree(max_rank)
count = 0
# ์ค๋ฅธ์ชฝ์์ ์ผ์ชฝ์ผ๋ก ์ฒ๋ฆฌ
for val in reversed(arr):
r = rank[val]
# r๋ณด๋ค ์์ ๊ฐ์ ๊ฐ์ (์ด๋ฏธ ์ฒ๋ฆฌ๋ = ์ค๋ฅธ์ชฝ์ ์๋)
count += bit.prefix_sum(r - 1)
bit.update(r, 1)
return count
# ์์
arr = [7, 5, 6, 4]
print(count_inversions(arr)) # 5: (7,5), (7,6), (7,4), (5,4), (6,4)
4.2 ๊ตฌ๊ฐ ์ ๋ฐ์ดํธ + ๊ตฌ๊ฐ ์ฟผ๋ฆฌ¶
class FenwickTreeRURQ:
"""
Range Update, Range Query
๋ ๊ฐ์ BIT ์ฌ์ฉ
"""
def __init__(self, n):
self.n = n
self.bit1 = [0] * (n + 2)
self.bit2 = [0] * (n + 2)
def _update(self, bit, i, delta):
while i <= self.n:
bit[i] += delta
i += i & (-i)
def _query(self, bit, i):
total = 0
while i > 0:
total += bit[i]
i -= i & (-i)
return total
def range_update(self, l, r, delta):
"""arr[l..r] += delta"""
self._update(self.bit1, l, delta)
self._update(self.bit1, r + 1, -delta)
self._update(self.bit2, l, delta * (l - 1))
self._update(self.bit2, r + 1, -delta * r)
def prefix_sum(self, i):
"""arr[1] + ... + arr[i]"""
return self._query(self.bit1, i) * i - self._query(self.bit2, i)
def range_sum(self, l, r):
"""arr[l] + ... + arr[r]"""
return self.prefix_sum(r) - self.prefix_sum(l - 1)
# ์์
bit = FenwickTreeRURQ(8)
bit.range_update(2, 5, 3) # arr[2..5] += 3
print(bit.range_sum(1, 4)) # 9 (0+3+3+3)
print(bit.range_sum(3, 6)) # 12 (3+3+3+3)
4.3 ์คํ๋ผ์ธ ์ฟผ๋ฆฌ ์ฒ๋ฆฌ¶
def offline_range_sum(arr, queries):
"""
์ฟผ๋ฆฌ: (l, r, type)
type 1: arr[l] += r
type 2: arr[l..r] ํฉ ๋ฐํ
"""
n = len(arr)
bit = FenwickTreeFromArray(arr)
results = []
for query in queries:
if query[0] == 1:
_, idx, val = query
bit.update(idx, val)
else:
_, l, r = query
results.append(bit.range_sum(l, r))
return results
5. 2D ํ์ ํธ๋ฆฌ¶
5.1 ๊ตฌํ¶
class FenwickTree2D:
def __init__(self, rows, cols):
self.rows = rows
self.cols = cols
self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]
def update(self, x, y, delta):
"""arr[x][y] += delta"""
i = x
while i <= self.rows:
j = y
while j <= self.cols:
self.tree[i][j] += delta
j += j & (-j)
i += i & (-i)
def prefix_sum(self, x, y):
"""arr[1..x][1..y] ํฉ"""
total = 0
i = x
while i > 0:
j = y
while j > 0:
total += self.tree[i][j]
j -= j & (-j)
i -= i & (-i)
return total
def range_sum(self, x1, y1, x2, y2):
"""arr[x1..x2][y1..y2] ํฉ"""
return (self.prefix_sum(x2, y2)
- self.prefix_sum(x1 - 1, y2)
- self.prefix_sum(x2, y1 - 1)
+ self.prefix_sum(x1 - 1, y1 - 1))
# ์์
bit2d = FenwickTree2D(4, 4)
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]
# ์ด๊ธฐํ
for i in range(4):
for j in range(4):
bit2d.update(i + 1, j + 1, matrix[i][j])
print(bit2d.range_sum(2, 2, 3, 3)) # 34 (6+7+10+11)
5.2 C++ 2D ๊ตฌํ¶
class FenwickTree2D {
private:
vector<vector<long long>> tree;
int rows, cols;
public:
FenwickTree2D(int r, int c) : rows(r), cols(c) {
tree.assign(r + 1, vector<long long>(c + 1, 0));
}
void update(int x, int y, long long delta) {
for (int i = x; i <= rows; i += i & (-i)) {
for (int j = y; j <= cols; j += j & (-j)) {
tree[i][j] += delta;
}
}
}
long long prefixSum(int x, int y) {
long long total = 0;
for (int i = x; i > 0; i -= i & (-i)) {
for (int j = y; j > 0; j -= j & (-j)) {
total += tree[i][j];
}
}
return total;
}
long long rangeSum(int x1, int y1, int x2, int y2) {
return prefixSum(x2, y2) - prefixSum(x1 - 1, y2)
- prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
}
};
6. ์ฐ์ต ๋ฌธ์ ¶
์ถ์ฒ ๋ฌธ์ ¶
| ๋์ด๋ | ๋ฌธ์ | ํ๋ซํผ | ์ ํ |
|---|---|---|---|
| โญโญโญ | ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ | ๋ฐฑ์ค | ๊ธฐ๋ณธ |
| โญโญโญ | Range Sum Query - Mutable | LeetCode | ๊ธฐ๋ณธ |
| โญโญโญ | ๋ฒ๋ธ ์ํธ | ๋ฐฑ์ค | ์ญ์ ์ |
| โญโญโญโญ | Count of Smaller Numbers | LeetCode | ์ญ์ ์ |
| โญโญโญโญ | ์ง์ฌ๊ฐํ ํฉ | ๋ฐฑ์ค | 2D BIT |
์ธ๊ทธ๋จผํธ ํธ๋ฆฌ vs ํ์ ํธ๋ฆฌ¶
โโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโ
โ ๊ธฐ์ค โ ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ โ ํ์
ํธ๋ฆฌ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโค
โ ๊ณต๊ฐ โ O(4n) โ O(n) โ
โ ๊ตฌํ ๋ณต์ก๋ โ ์ค๊ฐ โ ๊ฐ๋จ โ โ
โ ์์ ๊ณ์ โ ํผ โ ์์ โ โ
โ ์ ์ฟผ๋ฆฌ โ โ โ โ โ
โ ๊ตฌ๊ฐ ์ฟผ๋ฆฌ โ โ โ โ โ
โ ๊ตฌ๊ฐ ์
๋ฐ์ดํธ โ Lazy ํ์ โ 2๊ฐ BIT ํ์ โ
โ ๋ฒ์ฉ์ฑ โ ๋์ โ โ ๋ฎ์ (ํฉ๋ง) โ
โ ์ต์/์ต๋ โ โ โ โ โ
โโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโ
๊ฒฐ๋ก :
- ๊ตฌ๊ฐ ํฉ๋ง ํ์ โ ํ์
ํธ๋ฆฌ
- ์ต์/์ต๋/๋ณต์กํ ์ฐ์ฐ โ ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ
๋ค์ ๋จ๊ณ¶
- 25_Network_Flow.md - ๋คํธ์ํฌ ํ๋ก์ฐ