(11660) 구간 합 구하기 5

https://www.acmicpc.net/problem/11660

단계별로 풀어보기

22단계(누적 합) 5번째

 

 

 

구간합을 1차원이 아닌 2차원에서 구해야 하는 문제. 1차원에서 구간 (x,y)의 합을 구하는 공식이 s[y]-s[x-1]이었다면 2차원에서 구간 ((x1,y1),(x2,y2))의 합을 구하는 공식은 s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]이라는 것만 알면 된다.

x의 구간이 x1부터이므로 x1-1이전 구간을 빼고, y의 구간이 y1부터이므로 y1-1이전 구간을빼준다. 이때 양쪽 구간이 겹치는 부분은 두 번 빼지므로 한 번 더해줘야 한다.

말보다 그림으로 보면 더 이해가 쉬운데, 인터넷에 검색하면 많이 나오므로 여기서는 생략한다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector s(n+1, vector<int> (n+1));
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin >> s[i][j];
      s[i][j]+= s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    }
  }
  
  while(m--){
    int x1, y1, x2, y2;
    
    cin >> x1 >> y1 >> x2 >> y2;
    
    cout << s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] << "\n";
  }
  
  return 0;
}