24_fenwick_tree.cpp

Download
cpp 402 lines 11.8 KB 
  1/*
  2 * ํŽœ์œ… ํŠธ๋ฆฌ (Fenwick Tree / Binary Indexed Tree)
  3 * Point Update, Range Sum Query, 2D BIT
  4 *
  5 * ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋ณด๋‹ค ๊ฐ„๋‹จํ•˜๊ณ  ๋น ๋ฅธ ๊ตฌ๊ฐ„ ํ•ฉ ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <algorithm>
 11
 12using namespace std;
 13
 14// =============================================================================
 15// 1. ๊ธฐ๋ณธ ํŽœ์œ… ํŠธ๋ฆฌ (1-indexed)
 16// =============================================================================
 17
 18class FenwickTree {
 19private:
 20    vector<long long> tree;
 21    int n;
 22
 23public:
 24    FenwickTree(int n) : n(n), tree(n + 1, 0) {}
 25
 26    FenwickTree(const vector<int>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
 27        for (int i = 0; i < n; i++) {
 28            update(i + 1, arr[i]);
 29        }
 30    }
 31
 32    // arr[idx] += delta
 33    void update(int idx, long long delta) {
 34        while (idx <= n) {
 35            tree[idx] += delta;
 36            idx += idx & (-idx);  // ๋‹ค์Œ ๋…ธ๋“œ
 37        }
 38    }
 39
 40    // sum(arr[1..idx])
 41    long long prefixSum(int idx) {
 42        long long sum = 0;
 43        while (idx > 0) {
 44            sum += tree[idx];
 45            idx -= idx & (-idx);  // ๋ถ€๋ชจ ๋…ธ๋“œ
 46        }
 47        return sum;
 48    }
 49
 50    // sum(arr[l..r])
 51    long long rangeSum(int l, int r) {
 52        return prefixSum(r) - prefixSum(l - 1);
 53    }
 54};
 55
 56// =============================================================================
 57// 2. 0-indexed ํŽœ์œ… ํŠธ๋ฆฌ
 58// =============================================================================
 59
 60class FenwickTree0 {
 61private:
 62    vector<long long> tree;
 63    int n;
 64
 65public:
 66    FenwickTree0(int n) : n(n), tree(n, 0) {}
 67
 68    void update(int idx, long long delta) {
 69        while (idx < n) {
 70            tree[idx] += delta;
 71            idx |= (idx + 1);
 72        }
 73    }
 74
 75    long long prefixSum(int idx) {
 76        long long sum = 0;
 77        while (idx >= 0) {
 78            sum += tree[idx];
 79            idx = (idx & (idx + 1)) - 1;
 80        }
 81        return sum;
 82    }
 83
 84    long long rangeSum(int l, int r) {
 85        return prefixSum(r) - (l > 0 ? prefixSum(l - 1) : 0);
 86    }
 87};
 88
 89// =============================================================================
 90// 3. ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ์  ์ฟผ๋ฆฌ
 91// =============================================================================
 92
 93class FenwickTreeRangeUpdate {
 94private:
 95    vector<long long> tree;
 96    int n;
 97
 98    void update(int idx, long long delta) {
 99        while (idx <= n) {
100            tree[idx] += delta;
101            idx += idx & (-idx);
102        }
103    }
104
105    long long query(int idx) {
106        long long sum = 0;
107        while (idx > 0) {
108            sum += tree[idx];
109            idx -= idx & (-idx);
110        }
111        return sum;
112    }
113
114public:
115    FenwickTreeRangeUpdate(int n) : n(n), tree(n + 1, 0) {}
116
117    // arr[l..r] += delta
118    void updateRange(int l, int r, long long delta) {
119        update(l, delta);
120        update(r + 1, -delta);
121    }
122
123    // arr[idx]์˜ ํ˜„์žฌ ๊ฐ’
124    long long get(int idx) {
125        return query(idx);
126    }
127};
128
129// =============================================================================
130// 4. ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ๊ตฌ๊ฐ„ ์ฟผ๋ฆฌ
131// =============================================================================
132
133class FenwickTreeRangeRange {
134private:
135    vector<long long> tree1, tree2;
136    int n;
137
138    void update(vector<long long>& tree, int idx, long long delta) {
139        while (idx <= n) {
140            tree[idx] += delta;
141            idx += idx & (-idx);
142        }
143    }
144
145    long long query(const vector<long long>& tree, int idx) {
146        long long sum = 0;
147        while (idx > 0) {
148            sum += tree[idx];
149            idx -= idx & (-idx);
150        }
151        return sum;
152    }
153
154public:
155    FenwickTreeRangeRange(int n) : n(n), tree1(n + 1, 0), tree2(n + 1, 0) {}
156
157    // arr[l..r] += delta
158    void updateRange(int l, int r, long long delta) {
159        update(tree1, l, delta);
160        update(tree1, r + 1, -delta);
161        update(tree2, l, delta * (l - 1));
162        update(tree2, r + 1, -delta * r);
163    }
164
165    // sum(arr[1..idx])
166    long long prefixSum(int idx) {
167        return query(tree1, idx) * idx - query(tree2, idx);
168    }
169
170    // sum(arr[l..r])
171    long long rangeSum(int l, int r) {
172        return prefixSum(r) - prefixSum(l - 1);
173    }
174};
175
176// =============================================================================
177// 5. 2D ํŽœ์œ… ํŠธ๋ฆฌ
178// =============================================================================
179
180class FenwickTree2D {
181private:
182    vector<vector<long long>> tree;
183    int n, m;
184
185public:
186    FenwickTree2D(int n, int m) : n(n), m(m), tree(n + 1, vector<long long>(m + 1, 0)) {}
187
188    void update(int x, int y, long long delta) {
189        for (int i = x; i <= n; i += i & (-i)) {
190            for (int j = y; j <= m; j += j & (-j)) {
191                tree[i][j] += delta;
192            }
193        }
194    }
195
196    // sum from (1,1) to (x,y)
197    long long prefixSum(int x, int y) {
198        long long sum = 0;
199        for (int i = x; i > 0; i -= i & (-i)) {
200            for (int j = y; j > 0; j -= j & (-j)) {
201                sum += tree[i][j];
202            }
203        }
204        return sum;
205    }
206
207    // sum from (x1,y1) to (x2,y2)
208    long long rangeSum(int x1, int y1, int x2, int y2) {
209        return prefixSum(x2, y2)
210             - prefixSum(x1 - 1, y2)
211             - prefixSum(x2, y1 - 1)
212             + prefixSum(x1 - 1, y1 - 1);
213    }
214};
215
216// =============================================================================
217// 6. ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜ (Inversion Count)
218// =============================================================================
219
220long long countInversions(vector<int>& arr) {
221    int n = arr.size();
222
223    // ์ขŒํ‘œ ์••์ถ•
224    vector<int> sorted = arr;
225    sort(sorted.begin(), sorted.end());
226    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
227
228    for (int& x : arr) {
229        x = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
230    }
231
232    // BIT๋กœ ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜
233    FenwickTree bit(sorted.size());
234    long long inversions = 0;
235
236    for (int i = n - 1; i >= 0; i--) {
237        inversions += bit.prefixSum(arr[i] - 1);
238        bit.update(arr[i], 1);
239    }
240
241    return inversions;
242}
243
244// =============================================================================
245// 7. K๋ฒˆ์งธ ์›์†Œ ์ฐพ๊ธฐ
246// =============================================================================
247
248class FenwickTreeKth {
249private:
250    vector<long long> tree;
251    int n;
252
253public:
254    FenwickTreeKth(int n) : n(n), tree(n + 1, 0) {}
255
256    void update(int idx, long long delta) {
257        while (idx <= n) {
258            tree[idx] += delta;
259            idx += idx & (-idx);
260        }
261    }
262
263    // k๋ฒˆ์งธ ์›์†Œ์˜ ์ธ๋ฑ์Šค (1-indexed)
264    int kthElement(long long k) {
265        int idx = 0;
266        int bitMask = 1;
267        while (bitMask <= n) bitMask <<= 1;
268
269        for (; bitMask > 0; bitMask >>= 1) {
270            int next = idx + bitMask;
271            if (next <= n && tree[next] < k) {
272                k -= tree[next];
273                idx = next;
274            }
275        }
276
277        return idx + 1;
278    }
279};
280
281// =============================================================================
282// 8. ์ตœ์†Ÿ๊ฐ’ ํŽœ์œ… ํŠธ๋ฆฌ
283// =============================================================================
284
285class FenwickTreeMin {
286private:
287    vector<int> tree;
288    vector<int> arr;
289    int n;
290    const int INF = INT_MAX;
291
292public:
293    FenwickTreeMin(int n) : n(n), tree(n + 1, INF), arr(n + 1, INF) {}
294
295    // arr[idx] = val (val < ๊ธฐ์กด ๊ฐ’์ผ ๋•Œ๋งŒ ์œ ํšจ)
296    void update(int idx, int val) {
297        arr[idx] = val;
298        while (idx <= n) {
299            tree[idx] = min(tree[idx], val);
300            idx += idx & (-idx);
301        }
302    }
303
304    // min(arr[1..idx])
305    int prefixMin(int idx) {
306        int result = INF;
307        while (idx > 0) {
308            result = min(result, tree[idx]);
309            idx -= idx & (-idx);
310        }
311        return result;
312    }
313};
314
315// =============================================================================
316// ํ…Œ์ŠคํŠธ
317// =============================================================================
318
319int main() {
320    cout << "============================================================" << endl;
321    cout << "ํŽœ์œ… ํŠธ๋ฆฌ ์˜ˆ์ œ" << endl;
322    cout << "============================================================" << endl;
323
324    // 1. ๊ธฐ๋ณธ ํŽœ์œ… ํŠธ๋ฆฌ
325    cout << "\n[1] ๊ธฐ๋ณธ ํŽœ์œ… ํŠธ๋ฆฌ" << endl;
326    vector<int> arr = {1, 3, 5, 7, 9, 11};
327    FenwickTree ft(arr);
328    cout << "    ๋ฐฐ์—ด: [1, 3, 5, 7, 9, 11] (1-indexed)" << endl;
329    cout << "    sum[1, 3] = " << ft.rangeSum(1, 3) << endl;
330    cout << "    sum[2, 5] = " << ft.rangeSum(2, 5) << endl;
331    ft.update(3, 5);  // arr[3] += 5
332    cout << "    arr[3] += 5 ํ›„ sum[1, 3] = " << ft.rangeSum(1, 3) << endl;
333
334    // 2. ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ
335    cout << "\n[2] ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ์  ์ฟผ๋ฆฌ" << endl;
336    FenwickTreeRangeUpdate ftru(6);
337    ftru.updateRange(2, 4, 10);  // arr[2..4] += 10
338    cout << "    arr[2..4] += 10" << endl;
339    cout << "    arr[1] = " << ftru.get(1) << endl;
340    cout << "    arr[3] = " << ftru.get(3) << endl;
341    cout << "    arr[5] = " << ftru.get(5) << endl;
342
343    // 3. ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ๊ตฌ๊ฐ„ ์ฟผ๋ฆฌ
344    cout << "\n[3] ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ๊ตฌ๊ฐ„ ์ฟผ๋ฆฌ" << endl;
345    FenwickTreeRangeRange ftrr(6);
346    ftrr.updateRange(1, 3, 5);   // arr[1..3] += 5
347    ftrr.updateRange(2, 5, 10);  // arr[2..5] += 10
348    cout << "    arr[1..3] += 5, arr[2..5] += 10" << endl;
349    cout << "    sum[1, 6] = " << ftrr.rangeSum(1, 6) << endl;
350
351    // 4. 2D ํŽœ์œ… ํŠธ๋ฆฌ
352    cout << "\n[4] 2D ํŽœ์œ… ํŠธ๋ฆฌ" << endl;
353    FenwickTree2D ft2d(3, 3);
354    ft2d.update(1, 1, 1);
355    ft2d.update(1, 2, 2);
356    ft2d.update(2, 1, 3);
357    ft2d.update(2, 2, 4);
358    cout << "    3x3 ํ–‰๋ ฌ, (1,1)=1, (1,2)=2, (2,1)=3, (2,2)=4" << endl;
359    cout << "    sum[(1,1) to (2,2)] = " << ft2d.rangeSum(1, 1, 2, 2) << endl;
360
361    // 5. ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜
362    cout << "\n[5] ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜" << endl;
363    vector<int> invArr = {8, 4, 2, 1};
364    cout << "    ๋ฐฐ์—ด: [8, 4, 2, 1]" << endl;
365    cout << "    ์—ญ์ˆœ ์Œ: " << countInversions(invArr) << endl;
366
367    // 6. K๋ฒˆ์งธ ์›์†Œ
368    cout << "\n[6] K๋ฒˆ์งธ ์›์†Œ" << endl;
369    FenwickTreeKth ftkth(10);
370    ftkth.update(2, 1);  // 2 ์ถ”๊ฐ€
371    ftkth.update(5, 1);  // 5 ์ถ”๊ฐ€
372    ftkth.update(7, 1);  // 7 ์ถ”๊ฐ€
373    cout << "    ์ง‘ํ•ฉ: {2, 5, 7}" << endl;
374    cout << "    1๋ฒˆ์งธ ์›์†Œ: " << ftkth.kthElement(1) << endl;
375    cout << "    2๋ฒˆ์งธ ์›์†Œ: " << ftkth.kthElement(2) << endl;
376    cout << "    3๋ฒˆ์งธ ์›์†Œ: " << ftkth.kthElement(3) << endl;
377
378    // 7. ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ vs ํŽœ์œ… ํŠธ๋ฆฌ
379    cout << "\n[7] ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ vs ํŽœ์œ… ํŠธ๋ฆฌ" << endl;
380    cout << "    | ๊ธฐ์ค€           | ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ    | ํŽœ์œ… ํŠธ๋ฆฌ       |" << endl;
381    cout << "    |----------------|------------------|-----------------|" << endl;
382    cout << "    | ๊ตฌํ˜„ ๋ณต์žก๋„    | ์ค‘๊ฐ„             | ๋‚ฎ์Œ            |" << endl;
383    cout << "    | ๋ฉ”๋ชจ๋ฆฌ         | 4N               | N               |" << endl;
384    cout << "    | ์ƒ์ˆ˜ ๊ณ„์ˆ˜      | ํฌ๋‹ค             | ์ž‘๋‹ค            |" << endl;
385    cout << "    | ์ง€์› ์—ฐ์‚ฐ      | ๋‹ค์–‘             | ์ œํ•œ์           |" << endl;
386    cout << "    | Lazy ์ง€์›      | O                | ๋ณต์žก            |" << endl;
387
388    // 8. ๋ณต์žก๋„ ์š”์•ฝ
389    cout << "\n[8] ๋ณต์žก๋„ ์š”์•ฝ" << endl;
390    cout << "    | ์—ฐ์‚ฐ           | ์‹œ๊ฐ„๋ณต์žก๋„ | ๊ณต๊ฐ„๋ณต์žก๋„ |" << endl;
391    cout << "    |----------------|------------|------------|" << endl;
392    cout << "    | ์  ์—…๋ฐ์ดํŠธ    | O(log n)   | O(1)       |" << endl;
393    cout << "    | ๊ตฌ๊ฐ„ ํ•ฉ        | O(log n)   | O(1)       |" << endl;
394    cout << "    | ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ  | O(log n)   | O(n)       |" << endl;
395    cout << "    | 2D ์ฟผ๋ฆฌ        | O(logยฒ n)  | O(nm)      |" << endl;
396    cout << "    | K๋ฒˆ์งธ ์›์†Œ     | O(log n)   | O(1)       |" << endl;
397
398    cout << "\n============================================================" << endl;
399
400    return 0;
401}