사용자 도구

사이트 도구


ps:problems:boj:10999

구간 합 구하기 2

ps
링크acmicpc.net/…
출처BOJ
문제 번호10999
문제명구간 합 구하기 2
레벨플래티넘 4
분류

구간 쿼리

시간복잡도O(n + (m+k)logn)
인풋사이즈n<=1,000,000, m<=10,000, k<=10,000
사용한 언어Python
제출기록83764KB / 1144ms
최고기록1144ms
해결날짜2021/03/20
태그

48단계

풀이

  • 구간 업데이트와 구간 합 쿼리 를 요구하는 문제이다.
  • 세그먼트 트리의 lazy propagation을 필요로 하는 대표적인 문제이다. 이 경우 구간합과 구간 업데이트를 모두 O(logn)에 해결 가능하다.
  • 그리고, 2개의 펜윅 트리를 조합해서도 O(logn) 에 각 쿼리를 해결할 수 있는 것이 알려져 있다. n이 커지면, 이 방법이 세그먼트 트리보다 빠르게 동작한다. 자세한 것은 펜윅 트리 참고.
  • 트리를 구축하는 것에 O(n)이 걸리고, m+k개의 쿼리를 각각 O(logn)에 해결하므로, 전체 시간 복잡도는 O(n + (m+k)logn)

코드

"""Solution code for "BOJ 10999. 구간 합 구하기 2".

- Problem link: https://www.acmicpc.net/problem/10999
- Solution link: http://www.teferi.net/ps/problems/boj/10999
"""

import sys
from teflib import fenwicktree


def main():
    N, M, K = [int(x) for x in sys.stdin.readline().split()]
    range_fenwick = fenwicktree.RangeUpdatableFenwickTree(
        (int(sys.stdin.readline()) for _ in range(N)))
    for _ in range(M + K):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            a, b, c, d = query
            range_fenwick.range_update(b - 1, c, d)
        else:
            a, b, c = query
            print(range_fenwick.query(b - 1, c))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
D᠎ M V V A
 
ps/problems/boj/10999.txt · 마지막으로 수정됨: 2021/05/04 10:42 저자 teferi