목록누적합 (2)
주뇽's 저장소
Difference Array Technique 이 기법은 주로 누적 합(Prefix Sum)과 함께 사용되며, 배열의 연속적인 부분에 대한 업데이트를 빠르게 수행할 수 있도록 해준다. 효율적인 업데이트: 배열의 큰 구간을 한 번의 연산으로 업데이트할 수 있다. 이는 구간에 포함된 각 요소를 개별적으로 업데이트하는 것보다 훨씬 빠르다. 시간 복잡도: 각 업데이트는 O(1) 시간에 수행된다. 전체 배열에 대한 누적 합 계산은 O(N) 시간이 소요된다 예시: 온도 조절 상황 : 7일 동안의 온도 기록을 가지고 있다. 각 날짜의 초기 온도는 0도로 설정되어 있다. 일: 1 2 3 4 5 6 7 온도: 0 0 0 0 0 0 0 이제 다음과 같은 온도 조절 작업을 수행한다고 가정해 보자 : 1. 2일부터 4일까지..
https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 문제 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다. 입력 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거..