Algorithm/Problem Solving
[BOJ] 11660. 구간 합 구하기5 - JAVA 자바 ✨누적합✨
11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 누적합 2차원 배열에 대해 누적합을 저장하는 경우 O(N*N)의 시간 복잡도가 주어지지만, 합을 구하는 연산이 O(1)로 줄어든다. prefixSum[a][b] 를 (1,1)부터 (a,b) 까지의 합이라고 하자 왼쪽이 주어진 배열이고 오른쪽이 누적합을 저장한 이차원 배열이다. (1,1)에서 (2,3)까지의 누적합을 구하고자 하면 왼쪽 누적합과 위쪽 누적합을 더한 값에 교집합으로 두 번 더해지는 구간을 한 번 빼준 후 (2..
