[문제]
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.
[입력]
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.
입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
[출력]
첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
[예제]
>문제 풀이
인덱스 트리를 이용하여 풀었습니다.
처음 접하는 알고리즘으로 푸느라 사실 아직 이해를 제대로 했는지 모르겠습니다.
응용 문제가 많다고 하니 개념을 좀 더 살펴 본 후 관련 문제들을 더 풀어보면 좋을 것 같습니다.
인덱스 트리는 구간합을 구해야할 때, 중간에 인덱스의 값이 변하는 상황에서 쓰입니다.
배열로도 구간합을 저장할 수 있지만, 이 경우 특정 인덱스에 담긴 값을 바꿀 경우 배열 전체를 갈아엎어야 합니다..
그래서 이런 경우는 인덱스 트리를 사용하면 되는데, 포화 이진트리의 리프노드에 배열로 받은 값을 넣고 그 위로 구간합을 구하면서 올리는 구조입니다.
처음에 트리를 만들기 위해서는 Bottom-up으로 리프노드부터 위로 올라가는 방법을 쓰는데, 이후 query와(구간합 구하는 메소드) update에서는(특정 인덱스에 담긴 값을 변경) Top-down과 Bottom-up 2가지 방식으로 구현할 수 있습니다.
(알고리즘 수업에서 두 가지 방법으로 모두 구현해 보았지만, 이 문제에서는 top-down으로 제출하였습니다.)
**구현
1. N개의 배열값을 받았다면, 이제 인덱스 트리에 저장해야합니다.
인덱스 트리의 노드 개수는 2의 제곱수-1개 이고 리프 노드에 N개의 값을 저장해야 합니다.
근데 노드 번호는 0부터 시작하는데 연산을 0부터 하도록 구현하기 너무 번거롭습니다. 그래서 node[0]은 남겨두고 1부터 2N까지가 우리가 실제 값을 넣고 사용하는 노드입니다. 즉 트리의 인덱스 N~2N-1까지가 리프노드이고, 여기에 nums[N]을 담아야합니다.
=> N보다 크거나 같은 2의 제곱수가 리프노드의 개수 S이고, 2*S가 트리의 노드 개수 입니다.
ex) N=5 이면 S= 8(=2^3)
2. query ( left, right, node, queryLeft, queryRight)
left: 리프노드의 첫번째 인덱스(=1)
right: 리프노드의 마지막 인덱스(=S)
node: 현재 노드의 번호(Top-down으로 구현했으니 처음에 1로 넘긴다.)
queryLeft: 구하고자하는 구간의 왼쪽 인덱스
queryRight: 구하고자하는 구간의 오른쪽 인덱스
분기점을 3개로 나눠서 구현한다.
(1) (left, right): 현재노드가 담고있는 구간합의 구간과 (queryLeft, queryRight)와 범위가 겹치지 않는 경우
(2) (left, right)와 (queryLeft, queryRight)와 딱 맞는 경우
(3) (left, right)와 (queryLeft, queryRight)이 걸쳐있는 경우
:자식 노드들로 내려가서 필요한 값만 올릴 수 있도록 해야함.
: return query(왼쪽부분) + query(오른쪽 부분)
3. update(left, right, node, target, diff)
: 타겟을 찾아가며 타겟을 포함하는 구간합을 담은 노드에 +diff 처리를 해준다.
: diff 은 c - nums[target]
(c는 업데이트 해야할 값 , nums[target]은 업데이트 전의 값)
>전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static long nums[], tree[];
static int N, M, K, S;
public static void main(String[] args) throws IOException {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
N= Integer.parseInt(st.nextToken());
M= Integer.parseInt(st.nextToken());
K= Integer.parseInt(st.nextToken());
nums= new long[N];
for(int i=0; i<N; i++) {
nums[i]= Long.parseLong(br.readLine());
}
S=1;
while(S<N) {
S*=2;
}
tree= new long[S*2];
initBU();
int a, b;
long c;
for(int i=0; i<M+K; i++) {
st= new StringTokenizer(br.readLine());
a= Integer.parseInt(st.nextToken());
b= Integer.parseInt(st.nextToken());
c= Long.parseLong(st.nextToken());
if(a==1) { //1이면 업뎃
update(1, S, 1, b, c-nums[b-1]);
nums[b-1]=c;
}else if(a==2) { //2면 구간합
System.out.println(query(1, S, 1, b, c));
}
}
}//main
static void initBU() {
//Leaf에 값 반영
for(int i=0; i<N; i++) {
tree[S+i]=nums[i];
}
//내부노드 채움
for(int i=S-1; i>0; i--) {
tree[i]= tree[i*2]+tree[i*2+1];
}
}//init
static long query(int left, int right, int node, int queryLeft, long queryRight) {
// 연관이 없음
if(right<queryLeft||queryRight<left) {
return 0;
}
// 현재 노드가 쿼리 범위에 포함됨
else if(queryLeft<=left&&right<=queryRight) {
return tree[node];
}
// 현재 노드가(정확히는 구간이) 쿼리 범위에 포함은 안되는데, 겹침
else {
int mid= (left+right)/2;
long leftResult= query(left, mid, node*2, queryLeft, queryRight);
long rightResult= query(mid+1, right, node*2+1, queryLeft, queryRight);
return leftResult+rightResult;
}
}//query
static void update(int left, int right, int node, int target, long diff) {
//연관없음
if(target<left||right<target) return;
//연관 있음
tree[node]+=diff;
if(left!=right) {
int mid= (left+right)/2;
update(left, mid, node*2, target, diff);
update(mid+1, right, node*2+1, target, diff);
}
}//update
}'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
| [백준 알고리즘]11659번: 구간 합 구하기4_Java (0) | 2021.09.30 |
|---|---|
| [백준 알고리즘]11438번: LCA 2_Java (0) | 2021.09.30 |
| [백준 알고리즘]1202번: 보석도둑_Java (0) | 2021.09.30 |
| [백준 알고리즘]1806번: 부분합_Java (0) | 2021.08.03 |
| [백준 알고리즘] 3055번: 탈출_Java (0) | 2021.08.03 |
