[BOJ] 16975 수열과 쿼리 21

PS/BOJ 2020. 8. 24. 20:22

16975번: 수열과 쿼리 21

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다.

www.acmicpc.net

알고리즘: Segment tree

시간복잡도: $O(MlogN)$

접근:

이 문제는 분류를 보니 lazy propagation에 속해있던데 굳이 쓰지 않아도 쉽게 풀리는 문제다.

쿼리가 구간에 대해 묻는게 아니라 단순히 $A_x$를 출력하는거라서...

[l, r]에 k를 더하는 것을 segment tree에서 [l, r] 구간을 대표하는 노드에 k 값을 더해준 후,

$A_x$ 값을 찾을 때는 x번째 리프 부터 root까지 올라가면서 노드에 저장된 값들을 다 더해주었다.

펜윅 트리 200% 활용하기

흔히 lazy propagation을 사용하여 푸는 것으로 알려진 이 두 문제는 사실 펜윅 트리만으로 풀 수 있습니다. 구간 덧셈, 포인트 쿼리 다음 연산을 효율적으로 수행하는 자료구조를 만들어 봅시다. 이�

www.acmicpc.net

펜윅 트리 풀이도 재밌는 것 같음

코딩 코딩