[구름LEVEL] 후회

난이도	정답률
★★★★	-%

 

프리미엄 알고리즘 위클리 비타알고 시즌3 3월 5주차

goorm

문제

시행착오

7. Indexed Tree(BIT) & Range Sum

이 블로그가 도움이 많이 됐다. 처음에 누적합으로 했다가 갱신하는데 어차피 n*n 시간초과라서... 결국 검색을 했다. 'c++ 누적합 갱신' 이런식으로 검색했다가 찾은 블로그인데 정리가 잘 되어 있어서 좋았다. 

아래 코드는 indexed tree 를 이용해서 풀었고 '아직 93점. 15번 테스트케이스 틀림.' 상태이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
int n, m, base;
ll idt[1 << 27];
void update(int pos, int num) {
    idt[pos] -= num;
    pos >>= 1; // pos /= 2;
    while (pos) {
        idt[pos] = idt[pos * 2] + idt[pos * 2 + 1];
        pos /= 2;
    }
}
ll sum(int st, int end) {
    ll ret = 0;
    while (st < end) {
        if (st % 2 == 1) ret += idt[st], st++;
        if (!(end % 2)) ret += idt[end], end--;
        st >>= 1, end >>= 1;
    }
    if (st == end) ret += idt[st];
    return ret;
}
int main() {
    scanf("%d %d", &n, &m);
    for (base = 1; base < n; base *= 2);
    for (int i = base; i < base + n; i++) {
        scanf("%d", &idt[i]);
    }
    for (int i = base - 1; i > 0; i--) {
        idt[i] = idt[i * 2] + idt[i * 2 + 1];
    }
    while (m--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if (a == 1) {
            printf("%lld\n", sum(base + b - 1, base + c - 1));
        }
        else {
            update(base + b - 1, c);
        }
    }
 
    return 0;
}

해결

key point, indexed tree 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
int n, m, base;
ll idt[1 << 25];
void update(int pos, int num) {
    idt[pos] -= num;
    pos >>= 1; // pos /= 2;
    while (pos) {
        idt[pos] = idt[pos * 2] + idt[pos * 2 + 1];
        pos /= 2;
    }
}
ll sum(int st, int end) {
    ll ret = 0;
    while (st < end) {
        if (st % 2 == 1) ret += idt[st], st++;
        if (!(end % 2)) ret += idt[end], end--;
        st >>= 1, end >>= 1;
    }
    if (st == end) ret += idt[st];
    return ret;
}
int main() {
    scanf("%d %d", &n, &m);
    for (base = 1; base < n; base *= 2);
    for (int i = base; i < base + n; i++) {
        scanf("%d", &idt[i]);
    }
    for (int i = base - 1; i > 0; i--) {
        idt[i] = idt[i * 2] + idt[i * 2 + 1];
    }
    while (m--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if (a == 1) {
            printf("%lld\n", sum(base + b - 1, base + c - 1));
        }
        else {
            update(base + b - 1, c);
        }
    }
 
    return 0;
}

 

후기

와 그냥 너무 모르겠어서 코드 올려놓고 질문을 했더니 선생님???이 테스트케이스 오류라고 답변해주셔서 그대로 다시 제출하니까 정답떴다!! 이런적 처음이라 낯설고 기분좋다 ^^. 요즘 학교 사이버강의 듣고 과제하느라 너무 오랜만에 들어갔는데 좋은 소식있어서 너무 좋다~~