연속합과 쿼리

• 구간내 최대 연속부분합 쿼리, 일명 '금광세그' 쿼리 문제.
• 세그먼트 트리의 각 노드에 저장할 값과, 그 값을 합치는 방법이 조금 트리키하긴 하지만, 구현상으로는 Teferi library의 bottom-up 세그먼트 트리 구현체를 그대로 사용하는데에 아무 문제가 없다.
• 구간값을 합치는 것이 O(1)에 되므로, 각 쿼리는 O(logn)에 처리 가능하다. 그러면 트리 구축에 O(n)이 걸리고, m개의 쿼리를 각각 O(logn)에 처리하므로 총 시간 복잡도는 O(n+logm),

"""Solution code for "BOJ 16993. 연속합과 쿼리".

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

import sys
from teflib import segmenttree


def merge(l, r):
    l_lmax, l_rmax, l_max, l_all = l
    r_lmax, r_rmax, r_max, r_all = r
    return (max(l_lmax, l_all + r_lmax), max(r_rmax, l_rmax + r_all),
            max(l_max, r_max, l_rmax + r_lmax), l_all + r_all)


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    M = int(sys.stdin.readline())
    segtree = segmenttree.SegmentTree(((x, x, x, x) for x in A), merge)
    for _ in range(M):
        i, j = [int(x) for x in sys.stdin.readline().split()]
        print(segtree.query(i - 1, j)[2])


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree