코딩못하는사람

16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 1.접근 N은 십만 M도 십만이다. N^2으로 해결 불가능하고 NlogN으로 해결한다고 생각했다. 구간 합을 구하는 문제가 아닌 구간에 k를 더하는 문제이다. 생각을 조금 바꿔보자. 세그먼트 트리와 관련되서 생각해보니 1번 쿼리가 들어왔을 때 각 리프노드에 k를 더하지 않고 구간에 해당되는 노드에 k를 넣어놓고 출력할때 꺼내가면 된다고 생각했다. 2.풀이 우선 하던대로 완전 이진 트리를 리프노드만 전처리한다. 리프위에 노드들은 구간합같은 문제가..