acmicpc.net 10868(세그먼트 트리), 2357(세그먼트 트리), 2268(세그먼트 트리)

https://www.acmicpc.net/problem/10868

http://qkqhxla1.tistory.com/734 의 세그먼트트리를 조금 변경한다.

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

long long init(vector<long long> &a, vector<long long> &tree, int node, int start, int end) {
    if (start == end) {
        return tree[node] = a[start];
    } else {
        return tree[node] = min(init(a, tree, node*2, start, (start+end)/2), init(a, tree, node*2+1, (start+end)/2+1, end));
    }
}

long long sum(vector<long long> &tree, int node, int start, int end, int left, int right) {
    if (left > end || right < start) {
        return 999999999;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }
    return min(sum(tree, node*2, start, (start+end)/2, left, right), sum(tree, node*2+1, (start+end)/2+1, end, left, right));
}

int main() 
{
    int n, m;
    scanf("%d %d",&n,&m);
    vector<long long> a(n);
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h+1));
    vector<long long> tree(tree_size);
    for (int i=0; i<n; i++) {
        scanf("%lld",&a[i]);
    }
    init(a, tree, 1, 0, n-1);
    while (m--) {
        int t2,t3;
        scanf("%d %d",&t2,&t3);
        printf("%lld\n",sum(tree, 1, 0, n-1, t2-1, t3-1));
    }
    return 0;
}

https://www.acmicpc.net/problem/2357

최소값 세그먼트 트리와 최대값 세그먼트 트리 두개를 만들어서 각각 계산한다.

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

long long init0(vector<long long> &a, vector<long long> &tree, int node, int start, int end) {
    if (start == end) {
        return tree[node] = a[start];
    } else {
        return tree[node] = min(init0(a, tree, node*2, start, (start+end)/2), init0(a, tree, node*2+1, (start+end)/2+1, end));
    }
}
long long init1(vector<long long> &a, vector<long long> &tree, int node, int start, int end) {
    if (start == end) {
        return tree[node] = a[start];
    } else {
        return tree[node] = max(init1(a, tree, node*2, start, (start+end)/2), init1(a, tree, node*2+1, (start+end)/2+1, end));
    }
}

long long f0(vector<long long> &tree, int node, int start, int end, int left, int right) {
    if (left > end || right < start) {
        return 999999999;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }
    return min(f0(tree, node*2, start, (start+end)/2, left, right), f0(tree, node*2+1, (start+end)/2+1, end, left, right));
}
long long f1(vector<long long> &tree, int node, int start, int end, int left, int right) {
    if (left > end || right < start) {
        return 0;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }
    return max(f1(tree, node*2, start, (start+end)/2, left, right), f1(tree, node*2+1, (start+end)/2+1, end, left, right));
}

int main() 
{
    int n, m;
    scanf("%d %d",&n,&m);
    vector<long long> a(n);
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h+1));
    vector<long long> min_tree(tree_size);
	vector<long long> max_tree(tree_size);
    for (int i=0; i<n; i++) {
        scanf("%lld",&a[i]);
    }
    init0(a, min_tree, 1, 0, n-1);
	init1(a, max_tree, 1, 0, n-1);
    while (m--) {
        int t2,t3;
        scanf("%d %d",&t2,&t3);
        printf("%lld %lld\n",f0(min_tree, 1, 0, n-1, t2-1, t3-1), f1(max_tree, 1, 0, n-1, t2-1, t3-1));
    }
    return 0;
}

https://www.acmicpc.net/problem/2268

2042번이랑 똑같다. 다만 초기 배열을 0으로 설정하고 i>j일 경우에 대한 예외처리가 필요하다.

#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
long long init(vector<long long> &a, vector<long long> &tree, int node, int start, int end) {
    if (start == end) {
        return tree[node] = a[start];
    } else {
        return tree[node] = init(a, tree, node*2, start, (start+end)/2) + init(a, tree, node*2+1, (start+end)/2+1, end);
    }
}
void update(vector<long long> &tree, int node, int start, int end, int index, long long diff) {
    if (index < start || index > end) return;
    tree[node] = tree[node] + diff;
    if (start != end) {
        update(tree,node*2, start, (start+end)/2, index, diff);
        update(tree,node*2+1, (start+end)/2+1, end, index, diff);
    }
}
long long sum(vector<long long> &tree, int node, int start, int end, int left, int right) {
    if (left > end || right < start) {
        return 0;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }
    return sum(tree, node*2, start, (start+end)/2, left, right) + sum(tree, node*2+1, (start+end)/2+1, end, left, right);
}
int main() {
    int n, m;
    scanf("%d %d",&n,&m);
    vector<long long> a(n,0);
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h+1));
    vector<long long> tree(tree_size);

    init(a, tree, 1, 0, n-1);
    while (m--) {
        int t1,t2,t3;
        scanf("%d",&t1);
        if (t1 == 1) {
            int t2;
            long long t3;
            scanf("%d %lld",&t2,&t3);
            t2-=1;
            long long diff = t3-a[t2];
            a[t2] = t3;
            update(tree, 1, 0, n-1, t2, diff);
        } else if (t1 == 0) {
            int t2,t3;
            scanf("%d %d",&t2,&t3);
			if(t2>t3)
			{
				int tmp=t2;
				t2 = t3;
				t3 = tmp;
			}
            printf("%lld\n",sum(tree, 1, 0, n-1, t2-1, t3-1));
        }
    }
    return 0;
}