사용자 도구

사이트 도구


ps:problems:boj:2042

구간 합 구하기

ps
링크acmicpc.net/…
출처BOJ
문제 번호2042
문제명구간 합 구하기
레벨골드 1
분류

구간 쿼리

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

38단계, [라이]세그먼트 트리

풀이

  • 펜윅 트리나 세그먼트 트리를 사용하면, 트리를 만드는데에 O(n), 각 쿼리를 처리하는 데에 O(logn), 그래서 전체 O(n + (m+k)logn)에 해결 가능하다.
  • 이 문제에서는 쿼리가 최대 20000개인데, 이 정도 범위에서는 펜윅트리가 세그먼트 트리와 비슷하게 속도가 나거나 오히려 느리게 나오거나 했다.

코드

"""Solution code for "BOJ 2042. 구간 합 구하기".

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

import sys
from teflib import fenwicktree


def main():
    N, M, K = [int(x) for x in sys.stdin.readline().split()]
    nums = [int(sys.stdin.readline()) for _ in range(N)]
    fenwick = fenwicktree.FenwickTree(nums)
    for _ in range(M + K):
        a, b, c = [int(x) for x in sys.stdin.readline().split()]
        if a == 1:
            fenwick.set(b - 1, c)
        else:
            print(fenwick.query(b - 1, c))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L R B Q L
 
ps/problems/boj/2042.txt · 마지막으로 수정됨: 2022/07/08 01:51 저자 teferi