24_fenwick_tree.c

Download
c 393 lines 11.5 KB 
  1/*
  2 * ํŽœ์œ… ํŠธ๋ฆฌ (Fenwick Tree / Binary Indexed Tree)
  3 * ๊ตฌ๊ฐ„ ํ•ฉ, ์—ญ์ˆœ ์Œ, 2D BIT
  4 *
  5 * ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋ณด๋‹ค ๊ฐ„๋‹จํ•˜๊ณ  ๋ฉ”๋ชจ๋ฆฌ ํšจ์œจ์ ์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <string.h>
 11
 12#define MAX_N 100001
 13
 14/* =============================================================================
 15 * 1. ๊ธฐ๋ณธ ํŽœ์œ… ํŠธ๋ฆฌ (1-indexed)
 16 * ============================================================================= */
 17
 18typedef struct {
 19    long long* tree;
 20    int n;
 21} BIT;
 22
 23BIT* bit_create(int n) {
 24    BIT* bit = malloc(sizeof(BIT));
 25    bit->n = n;
 26    bit->tree = calloc(n + 1, sizeof(long long));
 27    return bit;
 28}
 29
 30void bit_free(BIT* bit) {
 31    free(bit->tree);
 32    free(bit);
 33}
 34
 35/* i๋ฒˆ์งธ ์›์†Œ์— delta ๋”ํ•˜๊ธฐ (1-indexed) */
 36void bit_update(BIT* bit, int i, long long delta) {
 37    for (; i <= bit->n; i += i & (-i)) {
 38        bit->tree[i] += delta;
 39    }
 40}
 41
 42/* [1, i] ๊ตฌ๊ฐ„ ํ•ฉ (1-indexed) */
 43long long bit_query(BIT* bit, int i) {
 44    long long sum = 0;
 45    for (; i > 0; i -= i & (-i)) {
 46        sum += bit->tree[i];
 47    }
 48    return sum;
 49}
 50
 51/* [l, r] ๊ตฌ๊ฐ„ ํ•ฉ (1-indexed) */
 52long long bit_range_query(BIT* bit, int l, int r) {
 53    return bit_query(bit, r) - bit_query(bit, l - 1);
 54}
 55
 56/* ๋ฐฐ์—ด๋กœ ์ดˆ๊ธฐํ™” */
 57void bit_build(BIT* bit, int arr[], int n) {
 58    for (int i = 1; i <= n; i++) {
 59        bit_update(bit, i, arr[i - 1]);
 60    }
 61}
 62
 63/* =============================================================================
 64 * 2. ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ์  ์ฟผ๋ฆฌ (Difference Array)
 65 * ============================================================================= */
 66
 67typedef struct {
 68    long long* tree;
 69    int n;
 70} BITDiff;
 71
 72BITDiff* bitd_create(int n) {
 73    BITDiff* bitd = malloc(sizeof(BITDiff));
 74    bitd->n = n;
 75    bitd->tree = calloc(n + 2, sizeof(long long));
 76    return bitd;
 77}
 78
 79void bitd_free(BITDiff* bitd) {
 80    free(bitd->tree);
 81    free(bitd);
 82}
 83
 84void bitd_update_internal(BITDiff* bitd, int i, long long delta) {
 85    for (; i <= bitd->n; i += i & (-i)) {
 86        bitd->tree[i] += delta;
 87    }
 88}
 89
 90/* [l, r] ๊ตฌ๊ฐ„์— delta ๋”ํ•˜๊ธฐ */
 91void bitd_range_update(BITDiff* bitd, int l, int r, long long delta) {
 92    bitd_update_internal(bitd, l, delta);
 93    bitd_update_internal(bitd, r + 1, -delta);
 94}
 95
 96/* i๋ฒˆ์งธ ์›์†Œ ๊ฐ’ ์กฐํšŒ */
 97long long bitd_point_query(BITDiff* bitd, int i) {
 98    long long sum = 0;
 99    for (; i > 0; i -= i & (-i)) {
100        sum += bitd->tree[i];
101    }
102    return sum;
103}
104
105/* =============================================================================
106 * 3. ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ๊ตฌ๊ฐ„ ์ฟผ๋ฆฌ
107 * ============================================================================= */
108
109typedef struct {
110    long long* tree1;
111    long long* tree2;
112    int n;
113} BITRange;
114
115BITRange* bitr_create(int n) {
116    BITRange* bitr = malloc(sizeof(BITRange));
117    bitr->n = n;
118    bitr->tree1 = calloc(n + 2, sizeof(long long));
119    bitr->tree2 = calloc(n + 2, sizeof(long long));
120    return bitr;
121}
122
123void bitr_free(BITRange* bitr) {
124    free(bitr->tree1);
125    free(bitr->tree2);
126    free(bitr);
127}
128
129void bitr_update_internal(long long* tree, int n, int i, long long delta) {
130    for (; i <= n; i += i & (-i)) {
131        tree[i] += delta;
132    }
133}
134
135long long bitr_query_internal(long long* tree, int i) {
136    long long sum = 0;
137    for (; i > 0; i -= i & (-i)) {
138        sum += tree[i];
139    }
140    return sum;
141}
142
143/* [l, r] ๊ตฌ๊ฐ„์— delta ๋”ํ•˜๊ธฐ */
144void bitr_range_update(BITRange* bitr, int l, int r, long long delta) {
145    bitr_update_internal(bitr->tree1, bitr->n, l, delta);
146    bitr_update_internal(bitr->tree1, bitr->n, r + 1, -delta);
147    bitr_update_internal(bitr->tree2, bitr->n, l, delta * (l - 1));
148    bitr_update_internal(bitr->tree2, bitr->n, r + 1, -delta * r);
149}
150
151/* [1, i] ๊ตฌ๊ฐ„ ํ•ฉ */
152long long bitr_prefix_sum(BITRange* bitr, int i) {
153    return bitr_query_internal(bitr->tree1, i) * i -
154           bitr_query_internal(bitr->tree2, i);
155}
156
157/* [l, r] ๊ตฌ๊ฐ„ ํ•ฉ */
158long long bitr_range_query(BITRange* bitr, int l, int r) {
159    return bitr_prefix_sum(bitr, r) - bitr_prefix_sum(bitr, l - 1);
160}
161
162/* =============================================================================
163 * 4. 2D ํŽœ์œ… ํŠธ๋ฆฌ
164 * ============================================================================= */
165
166typedef struct {
167    long long** tree;
168    int rows;
169    int cols;
170} BIT2D;
171
172BIT2D* bit2d_create(int rows, int cols) {
173    BIT2D* bit = malloc(sizeof(BIT2D));
174    bit->rows = rows;
175    bit->cols = cols;
176    bit->tree = malloc((rows + 1) * sizeof(long long*));
177    for (int i = 0; i <= rows; i++) {
178        bit->tree[i] = calloc(cols + 1, sizeof(long long));
179    }
180    return bit;
181}
182
183void bit2d_free(BIT2D* bit) {
184    for (int i = 0; i <= bit->rows; i++) {
185        free(bit->tree[i]);
186    }
187    free(bit->tree);
188    free(bit);
189}
190
191/* (x, y)์— delta ๋”ํ•˜๊ธฐ */
192void bit2d_update(BIT2D* bit, int x, int y, long long delta) {
193    for (int i = x; i <= bit->rows; i += i & (-i)) {
194        for (int j = y; j <= bit->cols; j += j & (-j)) {
195            bit->tree[i][j] += delta;
196        }
197    }
198}
199
200/* [(1,1), (x,y)] ์ง์‚ฌ๊ฐํ˜• ํ•ฉ */
201long long bit2d_query(BIT2D* bit, int x, int y) {
202    long long sum = 0;
203    for (int i = x; i > 0; i -= i & (-i)) {
204        for (int j = y; j > 0; j -= j & (-j)) {
205            sum += bit->tree[i][j];
206        }
207    }
208    return sum;
209}
210
211/* [(x1,y1), (x2,y2)] ์ง์‚ฌ๊ฐํ˜• ํ•ฉ */
212long long bit2d_range_query(BIT2D* bit, int x1, int y1, int x2, int y2) {
213    return bit2d_query(bit, x2, y2) -
214           bit2d_query(bit, x1 - 1, y2) -
215           bit2d_query(bit, x2, y1 - 1) +
216           bit2d_query(bit, x1 - 1, y1 - 1);
217}
218
219/* =============================================================================
220 * 5. ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜ (Inversion Count)
221 * ============================================================================= */
222
223long long count_inversions(int arr[], int n) {
224    /* ์ขŒํ‘œ ์••์ถ• */
225    int* sorted = malloc(n * sizeof(int));
226    memcpy(sorted, arr, n * sizeof(int));
227
228    /* ์ •๋ ฌ */
229    for (int i = 0; i < n - 1; i++) {
230        for (int j = i + 1; j < n; j++) {
231            if (sorted[i] > sorted[j]) {
232                int temp = sorted[i];
233                sorted[i] = sorted[j];
234                sorted[j] = temp;
235            }
236        }
237    }
238
239    /* ์ค‘๋ณต ์ œ๊ฑฐ ๋ฐ ์••์ถ• */
240    int* compressed = malloc(n * sizeof(int));
241    for (int i = 0; i < n; i++) {
242        int lo = 0, hi = n - 1;
243        while (lo < hi) {
244            int mid = (lo + hi) / 2;
245            if (sorted[mid] < arr[i]) lo = mid + 1;
246            else hi = mid;
247        }
248        compressed[i] = lo + 1;  /* 1-indexed */
249    }
250
251    /* ์—ญ์ˆœ ์Œ ์นด์šดํŠธ */
252    BIT* bit = bit_create(n);
253    long long inversions = 0;
254
255    for (int i = n - 1; i >= 0; i--) {
256        inversions += bit_query(bit, compressed[i] - 1);
257        bit_update(bit, compressed[i], 1);
258    }
259
260    bit_free(bit);
261    free(sorted);
262    free(compressed);
263    return inversions;
264}
265
266/* =============================================================================
267 * 6. K๋ฒˆ์งธ ์›์†Œ ์ฐพ๊ธฐ
268 * ============================================================================= */
269
270/* ๋ˆ„์ ํ•ฉ์ด k ์ด์ƒ์ด ๋˜๋Š” ์ตœ์†Œ ์ธ๋ฑ์Šค */
271int bit_find_kth(BIT* bit, long long k) {
272    int pos = 0;
273    int log_n = 0;
274    while ((1 << (log_n + 1)) <= bit->n) log_n++;
275
276    for (int i = log_n; i >= 0; i--) {
277        int next = pos + (1 << i);
278        if (next <= bit->n && bit->tree[next] < k) {
279            pos = next;
280            k -= bit->tree[pos];
281        }
282    }
283
284    return pos + 1;
285}
286
287/* =============================================================================
288 * ํ…Œ์ŠคํŠธ
289 * ============================================================================= */
290
291int main(void) {
292    printf("============================================================\n");
293    printf("ํŽœ์œ… ํŠธ๋ฆฌ (BIT) ์˜ˆ์ œ\n");
294    printf("============================================================\n");
295
296    /* 1. ๊ธฐ๋ณธ BIT */
297    printf("\n[1] ๊ธฐ๋ณธ ํŽœ์œ… ํŠธ๋ฆฌ\n");
298    int arr1[] = {1, 3, 5, 7, 9, 11};
299    int n1 = 6;
300    BIT* bit = bit_create(n1);
301    bit_build(bit, arr1, n1);
302
303    printf("    ๋ฐฐ์—ด: [1, 3, 5, 7, 9, 11]\n");
304    printf("    ๊ตฌ๊ฐ„ ํ•ฉ [1, 3]: %lld\n", bit_range_query(bit, 1, 3));
305    printf("    ๊ตฌ๊ฐ„ ํ•ฉ [1, 6]: %lld\n", bit_range_query(bit, 1, 6));
306    printf("    ๊ตฌ๊ฐ„ ํ•ฉ [3, 5]: %lld\n", bit_range_query(bit, 3, 5));
307
308    bit_update(bit, 3, 5);  /* arr[3]์— 5 ๋”ํ•˜๊ธฐ */
309    printf("    arr[3] += 5 ํ›„ ๊ตฌ๊ฐ„ ํ•ฉ [1, 6]: %lld\n", bit_range_query(bit, 1, 6));
310    bit_free(bit);
311
312    /* 2. ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ์  ์ฟผ๋ฆฌ */
313    printf("\n[2] ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ์  ์ฟผ๋ฆฌ\n");
314    BITDiff* bitd = bitd_create(5);
315
316    bitd_range_update(bitd, 1, 3, 10);  /* [1, 3]์— 10 ๋”ํ•˜๊ธฐ */
317    bitd_range_update(bitd, 2, 4, 5);   /* [2, 4]์— 5 ๋”ํ•˜๊ธฐ */
318
319    printf("    [1, 3]์— 10, [2, 4]์— 5 ๋”ํ•œ ํ›„:\n");
320    printf("    ");
321    for (int i = 1; i <= 5; i++) {
322        printf("arr[%d]=%lld ", i, bitd_point_query(bitd, i));
323    }
324    printf("\n");
325    bitd_free(bitd);
326
327    /* 3. ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ๊ตฌ๊ฐ„ ์ฟผ๋ฆฌ */
328    printf("\n[3] ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ, ๊ตฌ๊ฐ„ ์ฟผ๋ฆฌ\n");
329    BITRange* bitr = bitr_create(5);
330
331    bitr_range_update(bitr, 1, 3, 10);
332    bitr_range_update(bitr, 2, 5, 5);
333
334    printf("    [1, 3]์— 10, [2, 5]์— 5 ๋”ํ•œ ํ›„:\n");
335    printf("    ๊ตฌ๊ฐ„ ํ•ฉ [1, 5]: %lld\n", bitr_range_query(bitr, 1, 5));
336    printf("    ๊ตฌ๊ฐ„ ํ•ฉ [2, 4]: %lld\n", bitr_range_query(bitr, 2, 4));
337    bitr_free(bitr);
338
339    /* 4. 2D BIT */
340    printf("\n[4] 2D ํŽœ์œ… ํŠธ๋ฆฌ\n");
341    BIT2D* bit2d = bit2d_create(4, 4);
342
343    bit2d_update(bit2d, 1, 1, 1);
344    bit2d_update(bit2d, 2, 2, 2);
345    bit2d_update(bit2d, 3, 3, 3);
346    bit2d_update(bit2d, 2, 3, 4);
347
348    printf("    (1,1)=1, (2,2)=2, (3,3)=3, (2,3)=4 ์„ค์ •\n");
349    printf("    [(1,1), (3,3)] ํ•ฉ: %lld\n", bit2d_range_query(bit2d, 1, 1, 3, 3));
350    printf("    [(2,2), (3,3)] ํ•ฉ: %lld\n", bit2d_range_query(bit2d, 2, 2, 3, 3));
351    bit2d_free(bit2d);
352
353    /* 5. ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜ */
354    printf("\n[5] ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜\n");
355    int arr2[] = {8, 4, 2, 1};
356    printf("    ๋ฐฐ์—ด: [8, 4, 2, 1]\n");
357    printf("    ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜: %lld\n", count_inversions(arr2, 4));
358
359    int arr3[] = {1, 3, 2, 3, 1};
360    printf("    ๋ฐฐ์—ด: [1, 3, 2, 3, 1]\n");
361    printf("    ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜: %lld\n", count_inversions(arr3, 5));
362
363    /* 6. K๋ฒˆ์งธ ์›์†Œ */
364    printf("\n[6] K๋ฒˆ์งธ ์›์†Œ ์ฐพ๊ธฐ\n");
365    BIT* bit_kth = bit_create(10);
366    bit_update(bit_kth, 2, 1);  /* 2 ์ถ”๊ฐ€ */
367    bit_update(bit_kth, 5, 1);  /* 5 ์ถ”๊ฐ€ */
368    bit_update(bit_kth, 3, 1);  /* 3 ์ถ”๊ฐ€ */
369    bit_update(bit_kth, 7, 1);  /* 7 ์ถ”๊ฐ€ */
370
371    printf("    ์ง‘ํ•ฉ: {2, 3, 5, 7}\n");
372    printf("    1๋ฒˆ์งธ ์›์†Œ: %d\n", bit_find_kth(bit_kth, 1));
373    printf("    2๋ฒˆ์งธ ์›์†Œ: %d\n", bit_find_kth(bit_kth, 2));
374    printf("    3๋ฒˆ์งธ ์›์†Œ: %d\n", bit_find_kth(bit_kth, 3));
375    printf("    4๋ฒˆ์งธ ์›์†Œ: %d\n", bit_find_kth(bit_kth, 4));
376    bit_free(bit_kth);
377
378    /* 7. ๋ณต์žก๋„ */
379    printf("\n[7] ๋ณต์žก๋„ ๋น„๊ต (BIT vs ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ)\n");
380    printf("    | ์—ฐ์‚ฐ           | BIT        | ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ |\n");
381    printf("    |----------------|------------|---------------|\n");
382    printf("    | ์  ์—…๋ฐ์ดํŠธ    | O(log n)   | O(log n)      |\n");
383    printf("    | ๊ตฌ๊ฐ„ ํ•ฉ ์ฟผ๋ฆฌ   | O(log n)   | O(log n)      |\n");
384    printf("    | ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ  | O(log n)*  | O(log n)      |\n");
385    printf("    | ๊ณต๊ฐ„ ๋ณต์žก๋„    | O(n)       | O(4n)         |\n");
386    printf("    | ๊ตฌํ˜„ ๋‚œ์ด๋„    | ์‰ฌ์›€       | ์ค‘๊ฐ„          |\n");
387    printf("    * ๊ตฌ๊ฐ„ ์—…๋ฐ์ดํŠธ๋Š” ์ถ”๊ฐ€ ๋ฐฐ์—ด ํ•„์š”\n");
388
389    printf("\n============================================================\n");
390
391    return 0;
392}