세그먼트트리(segment tree)

구간합

#include <algorithm>
#include <vector>

using namespace std;

int segTree[100000];

int N, M;

void update(int n, int s, int e, int ii, int val) {
	if (s > ii || ii > e) return;
	segTree[n] += val;
	if (s == e) return;

	int m = (s + e) / 2;
	update(n * 2, s, m, ii, val);
	update(n * 2 + 1, m + 1, e, ii, val);
}

int query(int n, int s, int e, int l, int r) {
	if (e < l || s > r) return 0;
	if (s >= l && e <= r) return segTree[n];

	int m = (s + e) / 2;
	int a = query(n * 2, s, m, l, r);
	int b = query(n * 2 + 1, m + 1, e, l, r);
	return a + b;
}

구간합 + 최대, 최소

#include <algorithm>
#include <vector>

using namespace std;

struct Node {
    int sum;
    int maxVal; 
    int minVal;
};

Node segTree[100000];  // 세그먼트 트리

int N, M;

void update(int n, int s, int e, int ii, int val) {
    if (s > ii || ii > e) return;  // 범위 벗어나면 리턴
    if (s == e) {
        segTree[n].sum = segTree[n].maxVal = segTree[n].minVal = val;
        return;
    }

    int m = (s + e) / 2;
    update(n * 2, s, m, ii, val);         // 왼쪽 자식 업데이트
    update(n * 2 + 1, m + 1, e, ii, val); // 오른쪽 자식 업데이트

    // 구간 합, 최대값, 최소값 갱신
    segTree[n].sum = segTree[n * 2].sum + segTree[n * 2 + 1].sum;
    segTree[n].maxVal = max(segTree[n * 2].maxVal, segTree[n * 2 + 1].maxVal);
    segTree[n].minVal = min(segTree[n * 2].minVal, segTree[n * 2 + 1].minVal);
}

Node query(int n, int s, int e, int l, int r) {
    if (e < l || s > r) return {0, -1e9, 1e9};  // 범위를 벗어나면 초기값 리턴
    if (s >= l && e <= r) return segTree[n];  // 구간이 완전히 포함될 때

    int m = (s + e) / 2;
    Node left = query(n * 2, s, m, l, r);          // 왼쪽 자식 쿼리
    Node right = query(n * 2 + 1, m + 1, e, l, r); // 오른쪽 자식 쿼리

    // 쿼리 결과 병합
    Node res;
    res.sum = left.sum + right.sum;
    res.maxVal = max(left.maxVal, right.maxVal);
    res.minVal = min(left.minVal, right.minVal);
    return res;
}