구간 합 구하기 개념

 

 

1차원 누적합

 

 

 

배열[i] 부터 배열[j]의 값의 합을 여러번 구하는 문제가 나온다면 누적합배열을 생각할 수 있다.

누적합 배열을 만든다음 누적합배열[j]-누적합배열[i]를 뺴면 보다 복잡도가 낮게 구할 수 있다.

 

 

 

누적합 연산 뿐 아니다 구간 XOR 연산 과 곱셈에 또한 적용가능하다.

 

 

 

 

2차원 누적합

2차원은 원점으로 부터 i,j까지 사각형을 그려서 사각형을 이용한다.