1차원 누적합
배열[i] 부터 배열[j]의 값의 합을 여러번 구하는 문제가 나온다면 누적합배열을 생각할 수 있다.
누적합 배열을 만든다음 누적합배열[j]-누적합배열[i]를 뺴면 보다 복잡도가 낮게 구할 수 있다.
누적합 연산 뿐 아니다 구간 XOR 연산 과 곱셈에 또한 적용가능하다.
2차원 누적합
2차원은 원점으로 부터 i,j까지 사각형을 그려서 사각형을 이용한다.
'Problem Solving > 구간합' 카테고리의 다른 글
BOJ2295 세 수의 합 (1) | 2024.02.14 |
---|---|
BOJ17232 생명게임* (1) | 2024.02.11 |
BOJ 19951 태상이의 훈련소 생활 (0) | 2024.02.09 |
BOJ11660 구간 합 구하기 5(R) * (0) | 2024.02.09 |
BOJ16713 Generic Queries (0) | 2024.02.08 |