https://www.acmicpc.net/problem/12837
12837번: 가계부 (Hard)
살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려
www.acmicpc.net
쉽네요 ~ 세그먼트 트리 문제
시간 초과되는 부분만 조심해주면 됩니다.
package test01;
import java.util.*;
import java.io.*;
import java.lang.*;
import java.io.*;
public class Main {
public static long tree[];
public static long buildTree(int start, int end , int node , long arr[]) {
if(start==end) {
return tree[node]=arr[start];
}
int mid=(start+end)/2;
return tree[node]=buildTree(start,mid,node*2 ,arr)+ buildTree(mid+1,end,node*2+1,arr) ;
}
public static long select(int start, int end , int node, long left, long right) {
if (start > right || end < left) {
return 0;
}
if (start >= left && end <= right) {
return tree[node];
}
int mid=(start+end)/2;
return select(start,mid,node*2 ,left, right)+ select(mid+1,end,node*2+1 ,left, right) ;
}
public static void update(int start, int end , int node, long newValue,long findIndex) {
if (start > findIndex || end < findIndex) {
return;
}
if (start == end) {
tree[node] += newValue;
return;
}
int mid=(start+end)/2;
update(start,mid,node*2 ,newValue, findIndex);
update(mid+1,end,node*2+1 ,newValue, findIndex);
tree[node]= tree[node*2] + tree[node*2+1];
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder bz= new StringBuilder();
int n = Integer.parseInt(st.nextToken());
long arr[] = new long[n];
tree = new long[n * 4];
int m = Integer.parseInt(st.nextToken());
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
long b = Long.parseLong(st.nextToken());
long c = Long.parseLong(st.nextToken());
if (a == 1) {
update(0, n - 1, 1, c, b - 1);
} else {
long mins = select(0, n - 1, 1, Math.min(b, c) - 1, Math.max(b, c) - 1);
System.out.println(mins);
}
}
}
}'알고리즘 공부' 카테고리의 다른 글
| 백준 수열과 쿼리 37 (2) | 2024.07.15 |
|---|---|
| 백준 커피숍2 (0) | 2024.04.17 |
| 백준 쵯소값과 최댓값 (0) | 2024.04.08 |
| 백준 구간 합 구하기 (0) | 2024.04.04 |
| 백준 - 감시 (0) | 2024.04.04 |
