SegmentTree (구간 합)

 

1. 구간 합
2. 구간 곱
3. 구간 최솟값
4. 구간 최댓값
5. 구간 XOR
6. 인덱스가 값이 되는 경우, 값이 인덱스가 되는 경우
7. 구간 최대, 최소 인덱스

 

#include <vector>

using namespace std;

// node index 왼쪽 node * 2, 오른쪽 node * 2 + 1
// node index는 1부터 시작, vector index는 0부터 시작
class SegmentTree {
public:
    SegmentTree(int size): n(size) {
        tree.assign(4 * n, 0);
    }

    SegmentTree(const vector<long long>& arr): n(arr.size()) {
        tree.assign(4 * n, 0);
        build(arr, 1, 0, n - 1);
    }

    void update(int index, long long value) {
        update_util(1, 0, n - 1, index, value);
    }

    long long query(int left, int right) {
        return query_util(1, 0, n - 1, left, right);
    }

private:
    int n;
    vector<long long> tree;

    void build(const vector<long long>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, node * 2, start, mid);
            build(arr, node * 2 + 1, mid + 1, end);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

    void update_util(int node, int start, int end, int index, long long value) {
        if (start == end) {
            tree[node] += value; // 값 추가
            //tree[node] = value; //값 변경
            return;
        }

        int mid = (start + end) / 2;
        if (index <= mid) {
            update_util(node * 2, start, mid, index, value);
        } else {
            update_util(node * 2 + 1, mid + 1, end, index, value);
        }

        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    long long query_util(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return 0;
        }
        if (left <= start && end <= right) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        long long left_result = query_util(node * 2, start, mid, left, right);
        long long right_result = query_util(node * 2 + 1, mid + 1, end, left, right);

        return left_result + right_result;
    }
};