누적합-구간 합 구하기 5

일단 기본적으로 주어진 2차원 배열의 누적합을 생성한다.

누적합의 생성은 지점을 기준으로 윗칸의 누적합과 왼쪽칸의 누적합, 그리고 지점의 값을 전부 더하고 겹치는 부분만큼 빼주면서 순환하면 누적합의 배열을 생성할 수 있다.

  let prefix = [];

  for (let i = 0; i < size; i++) {
    prefix.push([]);
  }

  for (let y = 0; y < size; y++) {
    for (let x = 0; x < size; x++) {
      // 윗칸의 누적합
      const prefixTopValue = prefix[y - 1]?.[x] || 0;
      // 왼쪽칸의 누적합
      const prefixLeftValue = prefix[y]?.[x - 1] || 0;
      // 교집합 부분
      const intersectionValue = prefix[y - 1]?.[x - 1] || 0;
      // 지점 좌표
      const locationValue = list[y][x];

      const prefixValue =
        prefixTopValue + prefixLeftValue - intersectionValue + locationValue;

      prefix[y][x] = prefixValue;
    }
  }

그리고 최종적으로 구해야 하는건, 시작점과 끝점 좌표를 바탕으로 구간의 합을 구해야하는데,

끝점의 누적합(빨강) 에서 시작점 기준 윗줄과 왼쪽 줄을 빼준다음 곂치는 부분만큼 다시 더해주면 된다.

최종 코드

const Answer = (size, list, locations) => {
  let result = [];

  let prefix = [];

  for (let i = 0; i < size; i++) {
    prefix.push([]);
  }

  for (let y = 0; y < size; y++) {
    for (let x = 0; x < size; x++) {
      // 윗칸의 누적합
      const prefixTopValue = prefix[y - 1]?.[x] || 0;
      // 왼쪽칸의 누적합
      const prefixLeftValue = prefix[y]?.[x - 1] || 0;
      // 교집합 부분
      const intersectionValue = prefix[y - 1]?.[x - 1] || 0;
      // 지점 좌표
      const locationValue = list[y][x];

      const prefixValue =
        prefixTopValue + prefixLeftValue - intersectionValue + locationValue;

      prefix[y][x] = prefixValue;
    }
  }

  locations.forEach(i => {
    const [x1, y1, x2, y2] = i;
    // 끝 점 누적합
    const endPrefix = prefix[y2 - 1]?.[x2 - 1];
    // 윗 영역
    const topArea = prefix[y1 - 2]?.[x2 - 1] || 0;
    // 좌측 영역
    const leftArea = prefix[y2 - 1]?.[x1 - 2] || 0;
    // 교집합합
    const intersectionArea = prefix[y1 - 2]?.[x1 - 2] || 0;

    const value = endPrefix - topArea - leftArea + intersectionArea;
    result.push(value);
  });

  console.log(result);
};