단일 요소 수정 및 구간 질의

기본적인 세그먼트 트리는 이진 트리 구조로 단일 요소 수정과 구간 질의를 지원합니다:

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 200010;

struct TreeNode {
    int left, right, max_val;
} tree[MAX_N * 4];

void update_node(int idx) {
    tree[idx].max_val = max(tree[idx*2].max_val, tree[idx*2+1].max_val);
}

void construct_tree(int idx, int l, int r) {
    tree[idx] = {l, r};
    if (l == r) return;
    int mid = (l + r) / 2;
    construct_tree(idx*2, l, mid);
    construct_tree(idx*2+1, mid+1, r);
}

int get_max(int idx, int ql, int qr) {
    if (tree[idx].left >= ql && tree[idx].right <= qr) 
        return tree[idx].max_val;
    
    int mid = (tree[idx].left + tree[idx].right) / 2;
    int result = 0;
    if (ql <= mid) 
        result = get_max(idx*2, ql, qr);
    if (qr > mid) 
        result = max(result, get_max(idx*2+1, ql, qr));
    return result;
}

void change_value(int idx, int pos, int val) {
    if (tree[idx].left == pos && tree[idx].right == pos) {
        tree[idx].max_val = val;
    } else {
        int mid = (tree[idx].left + tree[idx].right) / 2;
        if (pos <= mid) change_value(idx*2, pos, val);
        else change_value(idx*2+1, pos, val);
        update_node(idx);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int operations, mod, count = 0, last = 0;
    cin >> operations >> mod;
    construct_tree(1, 1, operations);
    
    while (operations--) {
        char cmd;
        int value;
        cin >> cmd >> value;
        if (cmd == 'Q') {
            last = get_max(1, count - value + 1, count);
            cout << last << '\n';
        } else {
            change_value(1, count+1, (last + value) % mod);
            count++;
        }
    }
    return 0;
}

구간 합과 최대 부분배열

세그먼트 트리는 구간 합과 최대 부분배열 계산도 지원합니다:

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_SIZE = 2000010;

struct Segment {
    int l, r, total, prefix_max, suffix_max, max_sum;
} seg_tree[MAX_SIZE * 4];

void combine_nodes(Segment &parent, Segment &left, Segment &right) {
    parent.total = left.total + right.total;
    parent.prefix_max = max(left.prefix_max, left.total + right.prefix_max);
    parent.suffix_max = max(right.suffix_max, right.total + left.suffix_max);
    parent.max_sum = max({left.max_sum, right.max_sum, left.suffix_max + right.prefix_max});
}

void update_node(int idx) {
    combine_nodes(seg_tree[idx], seg_tree[idx*2], seg_tree[idx*2+1]);
}

void construct(int idx, int l, int r, int data[]) {
    if (l == r) {
        seg_tree[idx] = {l, r, data[l], data[l], data[l], data[l]};
    } else {
        seg_tree[idx] = {l, r};
        int mid = (l + r) / 2;
        construct(idx*2, l, mid, data);
        construct(idx*2+1, mid+1, r, data);
        update_node(idx);
    }
}

void modify_element(int idx, int pos, int val) {
    if (seg_tree[idx].l == pos && seg_tree[idx].r == pos) {
        seg_tree[idx] = {pos, pos, val, val, val, val};
    } else {
        int mid = (seg_tree[idx].l + seg_tree[idx].r) / 2;
        if (pos <= mid) modify_element(idx*2, pos, val);
        else modify_element(idx*2+1, pos, val);
        update_node(idx);
    }
}

Segment range_query(int idx, int ql, int qr) {
    if (seg_tree[idx].l >= ql && seg_tree[idx].r <= qr) 
        return seg_tree[idx];
    
    int mid = (seg_tree[idx].l + seg_tree[idx].r) / 2;
    if (qr <= mid) return range_query(idx*2, ql, qr);
    if (ql > mid) return range_query(idx*2+1, ql, qr);
    
    Segment left_part = range_query(idx*2, ql, qr);
    Segment right_part = range_query(idx*2+1, ql, qr);
    Segment result;
    combine_nodes(result, left_part, right_part);
    return result;
}

// 메인 함수 생략

구간 수정 및 질의

구간 덧셈 연산

#include <iostream>
using namespace std;
const int TREE_SIZE = 1000010;
typedef long long ll;

struct Node {
    int l, r;
    ll sum, lazy;
} seg[TREE_SIZE * 4];

void propagate(int idx) {
    if (seg[idx].lazy) {
        seg[idx*2].sum += (seg[idx*2].r - seg[idx*2].l + 1) * seg[idx].lazy;
        seg[idx*2].lazy += seg[idx].lazy;
        
        seg[idx*2+1].sum += (seg[idx*2+1].r - seg[idx*2+1].l + 1) * seg[idx].lazy;
        seg[idx*2+1].lazy += seg[idx].lazy;
        
        seg[idx].lazy = 0;
    }
}

void update_tree(int idx) {
    seg[idx].sum = seg[idx*2].sum + seg[idx*2+1].sum;
}

void build_tree(int idx, int l, int r, ll arr[]) {
    if (l == r) {
        seg[idx] = {l, r, arr[l], 0};
    } else {
        seg[idx] = {l, r};
        int mid = (l + r) / 2;
        build_tree(idx*2, l, mid, arr);
        build_tree(idx*2+1, mid+1, r, arr);
        update_tree(idx);
    }
}

void add_range(int idx, int ql, int qr, ll val) {
    if (seg[idx].l >= ql && seg[idx].r <= qr) {
        seg[idx].sum += (seg[idx].r - seg[idx].l + 1) * val;
        seg[idx].lazy += val;
        return;
    }
    propagate(idx);
    int mid = (seg[idx].l + seg[idx].r) / 2;
    if (ql <= mid) add_range(idx*2, ql, qr, val);
    if (qr > mid) add_range(idx*2+1, ql, qr, val);
    update_tree(idx);
}

ll query_sum(int idx, int ql, int qr) {
    if (seg[idx].l >= ql && seg[idx].r <= qr) 
        return seg[idx].sum;
    
    propagate(idx);
    int mid = (seg[idx].l + seg[idx].r) / 2;
    ll total = 0;
    if (ql <= mid) total += query_sum(idx*2, ql, qr);
    if (qr > mid) total += query_sum(idx*2+1, ql, qr);
    return total;
}

// 메인 함수 생략

다중 연산 동시 처리

#include <iostream>
using namespace std;
const int MOD_VAL = 10007;
const int MAX_NODES = 1000010;
typedef long long ll;

struct SegmentNode {
    int l, r;
    ll base_sum, sq_sum, cube_sum;
    ll add_tag, mul_tag, set_tag;
} seg_tree[MAX_NODES * 4];

void apply_set(SegmentNode &node, ll val) {
    node.set_tag = val;
    node.add_tag = 0;
    node.mul_tag = 1;
    ll len = node.r - node.l + 1;
    node.base_sum = len * val % MOD_VAL;
    node.sq_sum = len * val % MOD_VAL * val % MOD_VAL;
    node.cube_sum = len * val % MOD_VAL * val % MOD_VAL * val % MOD_VAL;
}

void apply_add(SegmentNode &node, ll val) {
    node.add_tag = (node.add_tag + val) % MOD_VAL;
    ll len = node.r - node.l + 1;
    node.cube_sum = (node.cube_sum + 3*val*node.sq_sum + 3*val*val*node.base_sum + len*val*val*val) % MOD_VAL;
    node.sq_sum = (node.sq_sum + 2*val*node.base_sum + len*val*val) % MOD_VAL;
    node.base_sum = (node.base_sum + len * val) % MOD_VAL;
}

void apply_mul(SegmentNode &node, ll val) {
    node.mul_tag = node.mul_tag * val % MOD_VAL;
    node.add_tag = node.add_tag * val % MOD_VAL;
    node.base_sum = node.base_sum * val % MOD_VAL;
    node.sq_sum = node.sq_sum * val % MOD_VAL * val % MOD_VAL;
    node.cube_sum = node.cube_sum * val % MOD_VAL * val % MOD_VAL * val % MOD_VAL;
}

// propagate 및 기타 함수 생략

영속적 세그먼트 트리

#include <iostream>
using namespace std;
const int MAX_VER = 1000010;

struct PersistentNode {
    int left, right, value;
} versions[25 * MAX_VER];
int version_count;

void build_version(int ver_id, int l, int r, int data[]) {
    if (l == r) {
        versions[ver_id].value = data[l];
        return;
    }
    versions[ver_id].left = ++version_count;
    versions[ver_id].right = ++version_count;
    int mid = (l + r) / 2;
    build_version(versions[ver_id].left, l, mid, data);
    build_version(versions[ver_id].right, mid+1, r, data);
}

void update_version(int &new_id, int old_id, int l, int r, int pos, int val) {
    new_id = ++version_count;
    versions[new_id] = versions[old_id];
    if (l == r) {
        versions[new_id].value = val;
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) 
        update_version(versions[new_id].left, versions[old_id].left, l, mid, pos, val);
    else 
        update_version(versions[new_id].right, versions[old_id].right, mid+1, r, pos, val);
}

int query_version(int ver_id, int l, int r, int pos) {
    if (l == r) return versions[ver_id].value;
    int mid = (l + r) / 2;
    if (pos <= mid) 
        return query_version(versions[ver_id].left, l, mid, pos);
    else 
        return query_version(versions[ver_id].right, mid+1, r, pos);
}

// 메인 함수 생략