2019. 3. 13. 16:55
# 문제링크
https://www.acmicpc.net/problem/2042
# 알고리즘
- Segment Tree를 사용해서 풀어야 한다.
- https://palyoung.tistory.com/64
# 풀이
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | package segment; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M, K; static int arr[]; public static void main(String[] args) throws IOException { //System.setIn(new FileInputStream("src\\sample.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); StringBuilder sb = new StringBuilder(); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); arr = new int[N]; int a=0, b=0, c=0; for (int i=0; i<N; i++) { arr[i] = Integer.parseInt(br.readLine()); } SegmentTree seg = new SegmentTree(arr, N); //seg.print(); for (int i=0; i<M+K; i++) { st = new StringTokenizer(br.readLine()); a = Integer.parseInt(st.nextToken()); b = Integer.parseInt(st.nextToken()); c = Integer.parseInt(st.nextToken()); // segment tree 업데이트 if (a == 1) { seg.update(b-1, c, 1, 0, N-1); } // segment tree에서 구간의 합 else if (a == 2) { sb.append(seg.query(b-1, c-1, 1, 0, N-1)+"\n"); } } System.out.println(sb); } } class SegmentTree { long SegmentTreeArr[]; // segment tree node 데이터 SegmentTree(int arr[], int N) { SegmentTreeArr = new long[N*4]; init(arr, 0, N-1, 1); } // Leaf Node가 N개인 Segment Tree 생성 // node 의 왼쪽 자식은 node*2, 오른쪽 자식은 node*2+1 long init(int arr[], int left, int right, int node) { // node가 리프 노드인 경우 if (left == right) return SegmentTreeArr[node] = arr[left]; int mid = (left+right)/2; return SegmentTreeArr[node] = init(arr, left, mid, node*2) + init(arr, mid+1, right, node*2+1); } // Segment Tree를 갱신하고 노드 구간의 합을 구한다. long update(int index, int value, int node, int nodeLeft, int nodeRight) { // index가 Node 구간에 포함되지 않는 경우 if (index < nodeLeft || index > nodeRight) return SegmentTreeArr[node]; // node가 리프 노드인 경우 if (nodeLeft == nodeRight) return SegmentTreeArr[node] = value; int mid = (nodeLeft + nodeRight)/2; return SegmentTreeArr[node] = update(index, value, node*2, nodeLeft, mid) + update(index, value, node*2+1, mid+1, nodeRight); } // Segment Tree의 구간 합을 구한다. long query(int left, int right, int node, int nodeLeft, int nodeRight) { // 두 구간이 겹치지 않는 경우 if (left > nodeRight || right < nodeLeft) return 0; // [left, right]가 [nodeLeft, nodeRight]를 포함하는 경우 if (left <= nodeLeft && right >= nodeRight) return SegmentTreeArr[node]; int mid = (nodeLeft + nodeRight)/2; return query(left, right, node*2, nodeLeft, mid) + query(left, right, node*2+1, mid+1, nodeRight); } void print() { for (int i=0; i<SegmentTreeArr.length; i++) { System.out.printf("%d, ", SegmentTreeArr[i]); } System.out.println(); } } | cs |
'PS(Problem Solving) > Segment Tree' 카테고리의 다른 글
| 최솟값과 최댓값 (0) | 2019.03.14 |
|---|---|
| [BOJ]10868. 최솟값 (0) | 2019.03.13 |