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


인덱스 트리를 활용하여 해결했다.


앞선 인덱스 트리를 활용하는 문제들과 같이, 이 문제도 말만 다르지, 결국 원소 업데이트가 빈번하게 일어나는 동시에 구간합을 구하는 문제이다.


특정 맛의 사탕을 빼거나 더하는 것은, 인덱스 트리의 기본적인 업데이트 쿼리와 동일하기 때문에 따로 설명하지는 않을 것이고, 특정 순위의 사탕을 가져오는 부분에 대해서만 살펴보겠다.



a == 1인 경우에 k번째 순위를 가지는 사탕을 가져와야 하는 상황이다.


root에서부터 노드 하나하나가 사탕의 개수를 구간합으로 가지고 있는 형태로 트리를 만들어준다. leaf 노드의 수는 가능한 맛의 범위로 잡아주면 된다. 이 문제에서는 100 만이었던 것으로 기억한다.


이렇게 leaf 노드는 그 맛의 사탕이 몇 개 있다는 것을 의미한다.



이제 k번째 순위의 사탕을 찾는다고 하면, 트리의 왼쪽에서부터(가장 맛있는 사탕부터) k번째인 것이다. 이때 k보다 한 노드의 값(거기까지 구간합)이 크다면 그 노드의 자손 부분에 우리가 찾는 k번째 사탕이 존재한다는 의미이므로 계속 아래로 내려가준다.


반대로 k보다 작다면, 우리가 찾는 k번째 사탕이 그 노드의 오른쪽 트리에 있다는 것이기 때문에 오른쪽으로 이동해주고, 왼쪽에 있는 사탕의 개수(확인했던 구간합의 값)만큼 k를 감소시켜준다.


또한 리트 노드에 도달했다면 위의 작업을 해줄 필요가 없기 때문에, 리프 노드인지 아닌지 확인해 주는 작업을 함께 진행해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#define MAX 1000000
using namespace std;
 
int idxT[4 * MAX+2], start = 1;
 
void Update(int idx, int delta) {
    while (idx > 0) {
        idxT[idx] += delta;
        idx /= 2;
    }
}
 
int getCandy(int k) {
    int i = 1;
    while (1) {
        if (idxT[i] >= k) { //이 지점의 서브트리에 우리가 찾는 사탕이 속해 있다면
            if (i >= start && i < start + MAX) { //그 지점이 leaf라면 종료
                Update(i, -1);
                return i - start + 1;
            }
            i *= 2; //leaf가 아니라면 이어서 탐색
            continue;
        }
        else { //이 지점이 아닌 반대쪽에 우리가 찾는 사탕이 있다면
            k = k - idxT[i]; 
            i++;
            continue;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    while (start < MAX) //MAX보다 크거나 같으면서 가장 큰 2의 제곱수
        start *= 2;
    
    int n; 
    cin >> n; //쿼리의 수
    for (int i = 0, a, b, c ; i < n; i++) {
        cin >> a >> b;
        if (a == 1) 
            cout << getCandy(b) << '\n'; //사탕 꺼내기
        
        else {
            cin >> c; //사탕의 변화량
            Update(b + start - 1, c);
        }
    }
    
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13

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


수열의 성분이 빈번하게 바뀌면서, 구간합을 물어보는 문제이기 때문에 인덱스 트리를 구현해주면 된다.


인덱스 트리에 대한 좀 더 자세한 설명은 https://hugssy.tistory.com/132 를 참고하면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll idxTree[4 * 100002];
ll findSum(int st, int en) {
    ll ret = 0;
    while (st <= en) {
        if (st % 2 == 1) ret += idxTree[st];
        if (en % 2 == 0) ret += idxTree[en];
        st = (st + 1) / 2;
        en = (en - 1) / 2;
    }
    return ret;
}
void Update(int idx, ll delta) {
    while (idx > 0) {
        idxTree[idx] += delta;
        idx /= 2;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q;
    cin >> n >> q;
 
    int start = 1;
    while (start < n)
        start *= 2; //n보다 큰 가장 작은 2의 제곱수
 
    for (int i = 0; i < n; i++)
        cin >> idxTree[i + start];
 
    for (int i = start - 1; i >= 1; i--)
        idxTree[i] = idxTree[2 * i] + idxTree[2 * i + 1];
 
    while (q--) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        if (x > y) swap(x, y);
        cout << findSum(x + start - 1, y + start - 1) << '\n';
        Update(a + start - 1, b - idxTree[a + start - 1]);
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13
백준 2042번 구간합 구하기 C++  (0) 2019.08.13

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


일반적인 구간합 구하기 문제라면, 배열을 별도로 두고 특정 인덱스까지 구간합을 저장해서 구하겠지만,


이 문제의 경우처럼 원소 자체가 빈번하게 업데이트 되면서 구간합을 구해야 한다면 인덱스 트리를 사용하는 게 편리하다.



인덱스 트리를 만드는 과정은 다음과 같다.


우선 leaf가 꽉 찬 트리로 만들어야 하기 때문에 원소의 개수보다 큰 가장 작은 2의 제곱수를 찾는다.


가령 예시의 경우처럼 원소가 5개라면 5보다 큰 가장 작은 2의 제곱수는 8이다.


기본적으로 배열은 1-indexed로 한다. 따라서 leaf에 처음 숫자들이 저장될 텐데, 인덱스 8부터 들어가면 된다.


비는 공간은 쿼리와 상관없는 수로 채워준다. (구간합 구하기 문제 같은 경우 0은 합에 영향을 미치지 않기 때문에 0으로 채워준다)


(가령 구간의 최댓값을 저장하는 인덱스 트리라면 구간의 최댓값에 영향을 미치지 않게 가장 작은 수로 비는 부분을 채워주면 된다)



인덱스를 찾았으니 구간합을 채워주면 된다.


부모의 인덱스는 자식 인덱스 /2, 왼쪽 자식은 부모 인덱스 *2, 오른쪽은 *2 +1 이라는 것을 이용해서 쿼리를 만들어주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#define MAX 1000002
using namespace std;
 
typedef long long ll;
ll idxTree[4 * MAX];
 
void Update(int idx, ll delta) {
    while (idx > 0) {
        idxTree[idx] += delta;
        idx /= 2;
    }
}
 
ll findSum(int st, int en) {
    ll ret = 0;
    while (st <= en) {
        if (st % 2 == 1) ret += idxTree[st];
        if (en % 2 == 0) ret += idxTree[en];
        st = (st + 1) / 2;
        en = (en - 1) / 2;
    }
    return ret;
}
 
int main(void) {
    int n, m, k;
    cin >> n >> m >> k;
    int start = 1;
    while (start < n) {
        start *= 2; //n보다 큰 가장 작은 2의 제곱수
    }
    
    for (int i = 0; i < n; i++) { //원래 빈공간도 채워줘야 한다. 쿼리에 영향을 받지 않는 값으로
        cin >> idxTree[start + i];
    }
    //트리의 아래에서 위로 채워가기
    for (int i = start - 1; i >= 1; i--) {
        idxTree[i] = idxTree[2 * i] + idxTree[2 * i + 1];
    }
    for (int i = 0; i < m + k; i++) {
        int a, b, c;
        cin >> a >> b >> c; //두 경우 모두 인덱스를 계산해서 넘겨야함, 차이는 새거-있던거
        if (a == 1) Update(b + start - 1, c - idxTree[b + start - 1]);
        else if (a == 2) cout << findSum(b + start - 1, c + start - 1) << '\n';
    }
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13
백준 3878 점 분리 C++  (0) 2019.08.12
백준 1708 볼록 껍질 C++  (0) 2019.08.12

+ Recent posts

티스토리툴바