사용자 도구

사이트 도구


ps:problems:boj:14438

수열과 쿼리 17

ps
링크https://www.acmicpc.net/problem/14438
출처BOJ
문제 번호14438
문제명수열과 쿼리 17
레벨골드 1
분류

구간 쿼리

시간복잡도O(n+mlogn)
인풋사이즈n<=100,000, m<=100,000
사용한 언어Python
제출기록44656KB / 1256ms
최고기록1068ms
해결날짜2021/03/20

풀이

  • 업데이트 쿼리와 구간 최솟값 쿼리가 주어지는 문제이다.
  • 세그먼트 트리를 이용해서 업데이트와 구간최솟값 쿼리를 모두 O(logn)에 처리 가능하다.
  • 구간 합과는 달리, 펜윅트리는 일반적인 방법으로는 적용이 불가능하다.
    • 펜윅트리 2개를 조합해서 처리하는 방법이 존재하긴 하고, 그 방법이 더 빠르다고는 하다. 펜윅 트리 참고. 하지만 구현해보지는 않았다
  • 세그먼트 트리를 구축하는 데에 O(n)이 걸리고 m개의 쿼리를 각각 O(logn)에 처리하므로, 총 시간 복잡도는 O(n+mlogn)

코드

"""Solution code for "BOJ 14438. 수열과 쿼리 17".

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

import sys
from teflib import segmenttree


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    A = [int(x) for x in sys.stdin.readline().split()]
    segtree = segmenttree.SegmentTree(A)
    M = int(sys.stdin.readline())
    for i in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, i, v = query
            segtree.set(i - 1, v)
        else:
            _, i, j = query
            print(segtree.query(i - 1, j))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L I S X I
 
ps/problems/boj/14438.txt · 마지막으로 수정됨: 2021/04/30 15:17 저자 teferi