인덱스 트리

비트연산 활용 => 구간 합

특징 : 세그먼트 트리와 성능적으론 비슷 but, 메모리 측면에선 더 효율적

1. 특정한 숫자의 마지막 비트 구하기
2. 값 update
3. 합 구하기
4. 특정 구간의 합 구하기

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 47 48 49 50

#define _CRT_SECURE_NO_WARNINGS #define INF 987654321     #include <iostream>     using namespace std;   const int num = 6; int arr[num];   void update(int n, int diff) { // 2. 값 update          while (n < num) {         arr[n] += diff;         n += (n & -n); // 1. 특정한 숫자의 마지막 비트 구하기     } }   int sum(int n) { // 3. 합 구하기          int temp = 0;       while (n > 0) {                  temp += arr[n];         n -= (n & -n);     }       return temp; }   int getSum(int start, int end) { // 4. 특정 구간의 합 구하기     return sum(end) - sum(start - 1); }   int main() {     update(1, 1);     update(2, 2);     update(3, 3);     update(4, 4);     update(5, 5);       cout << sum(4) << endl;     cout << getSum(4, 5) << endl;       return 0; } Colored by Color Scripter

cs