(백준 2042번 구간 합 구하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 1

나의 스승 라이님 블로그를 보고 오늘은 세그먼트 트리를 배워보았다.

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220791986409&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

세그먼트 트리(Segment Tree) (수정: 2019-02-12)

 

풀이는 라이님 깃허브에서 가져옴!!

https://github.com/kks227/BOJ/blob/master/2000/2042.cpp

BOJ/2000/2042.cpp at master · kks227/BOJ

 

라이님 풀이를 템플릿 삼아 알고리즘을 잘 익히고 있는지라.. 살짝쿵 가져왔

// 출처 : https://github.com/kks227/BOJ/blob/master/2000/2042.cpp
#include <cstdio>
#include <cstring>
using namespace std;
const int SIZE = 2097152;

struct SegTree {
	int size, start;
	long long arr[SIZE];
	SegTree(int n) : size(n) {
		start = 1;
		while (start < size) start *= 2;
		memset(arr, 0, sizeof(arr));
	}
	void construct() {
		for (int i = start - 1; i > 0; i--)
			arr[i] = arr[i * 2] + arr[i * 2 + 1];
	}
	void add(int a, long long b) {
		a += start;
		b -= arr[a];
		while (a > 0) {
			arr[a] += b;
			a /= 2;
		}
	}
	long long sum(int a, int b) { return sum(a, b, 1, 0, start); }
	long long sum(int a, int b, int node, int na, int nb) {
		if (b <= na || nb <= a) return 0;
		if (a <= na && nb <= b) return arr[node];
		int mid = (na + nb) / 2;
		return sum(a, b, node * 2, na, mid) + sum(a, b, node * 2 + 1, mid, nb);
	}
};

int main() {
	int N, M, K;
	scanf("%d %d %d", &N, &M, &K);
	SegTree ST(N);
	for (int i = 0; i < N; i++)
		scanf("%lld", ST.arr + ST.start + i);
	ST.construct();
	for (int i = 0; i < M + K; i++) {
		int a;
		scanf("%d", &a);
		if (a == 1) {
			int b;
			long long c;
			scanf("%d %lld", &b, &c);
			ST.add(b - 1, c);
		}
		else {
			int b, c;
			scanf("%d %d", &b, &c);
			printf("%lld\n", ST.sum(b - 1, c));
		}
	}
}

 

여기 있는 템플릿을 잘 이용해서 남은 문제들도 잘 풀어보아야겠다!!!! 룰루 !

← 이 다짐이 무색하게... 너무 고생했다..

 

일단 arr을 int의 배열로 잡아놓으니 스택에 너무 큰 크기가 잡히는지 나의 visual studio에서 돌아가지 않았다.

그래서 vector로 바꾸면서 이것저것 바꿨는데,,

 

진짜 뭐가 문제인지 모르겠는데 자꾸 안 돌아서 라이님 풀이를 놓고 비교하기 시전ㅋㅋㅋㅋㅋㅋ

중간에 맞은건 라이님의 풀이,, vector를 써서 다시 겨우 풀었다(?)

풀었다는 말이 맞는지 모르겠지만 하여튼...!

아래 풀이를 템플릿으로 얼른 세그먼트 트리 뽀개야징~

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>

using namespace std;

struct segTree {
    int n, start;
    vector<long long> arr;

    segTree(int n) : n(n) {
        start = 1;
        while (start < n) start *= 2;
        arr.resize(2 * start); // 더 안전하게 배열 크기를 설정
        fill(arr.begin(), arr.end(), 0);
    }

    void construct() {
        for (int i = start - 1; i > 0; i--)
            arr[i] = arr[i * 2] + arr[i * 2 + 1];
    }

    void add(int a, long long b) {
        a += start;
        b -= arr[a];
        while (a > 0) {
            arr[a] += b;
            a /= 2;
        }
    }
    long long sum(int a, int b, int node, int na, int nb) {
        if (nb <= a || b <= na) return 0;
        if (a <= na && nb <= b) return arr[node];
        int mid = (na + nb) / 2;
        return sum(a, b, node * 2, na, mid) + sum(a, b, node * 2 + 1, mid, nb);
    }
    long long sum(int a, int b) { return sum(a, b, 1, 0, start); }
};

int main() {
    int N, M, K; scanf("%d %d %d", &N, &M, &K);
    segTree st(N);

    for (int i = 0; i < N; i++) {
        scanf("%lld", &st.arr[i + st.start]);
    }

    st.construct();
    int a, b; long long c;
    for (int i = 0; i < M + K; i++) {
        scanf("%d %d %lld", &a, &b, &c);
        if (a == 1) {
            st.add(b - 1, c);
        }
        else if (a == 2) {
            printf("%lld\n", st.sum(b - 1, c));
        }
    }
    return 0;
}