[1275]커피숍2
//세그먼트 트리
import java.util.*;
import java.io.*;
public class Main {
static int N, Q;
static long answer, tree[], arr[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
arr = new long[N + 1];
tree = new long[(N + 1) * 4];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Long.parseLong(st.nextToken());
}
init(1, N, 1);
for (int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
long b = Long.parseLong(st.nextToken());
if (x > y) {
int temp = x;
x = y;
y = temp;
}
sb.append(sum(1, N, 1, x, y)).append("\n");
update(1, N, 1, a, b - arr[a]);
arr[a] = b;
}
System.out.println(sb);
}
//초기화
static long init(int start, int end, int node) {
if (start == end)
return tree[node] = arr[start];
int mid = (start + end) / 2;
return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}
//업데이트
static void update(int start, int end, int node, int index, long diff) {
if (start > index || end < index)
return;
tree[node] += diff;
if (start == end)
return;
int mid = (start + end) / 2;
update(start, mid, node * 2, index, diff);
update(mid + 1, end, node * 2 + 1, index, diff);
}
//합구하기
static long sum(int start, int end, int node, int l, int r) {
if (start > r || end < l)
return 0;
else if (l <= start && end <= r)
return tree[node];
int mid = (start + end) / 2;
return sum(start, mid, node * 2, l, r) + sum(mid + 1, end, node * 2 + 1, l, r);
}
}
//펜윅트리
import java.util.*;
import java.io.*;
public class Main {
static int N, Q;
static long answer, tree[], arr[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
arr = new long[N + 1];
tree = new long[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Long.parseLong(st.nextToken());
update(i, arr[i]);
}
for (int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
long b = Long.parseLong(st.nextToken());
if (x > y) {
int temp = x;
x = y;
y = temp;
}
sb.append(sum(y) - sum(x - 1)).append("\n");
update(a, b - arr[a]);
arr[a] = b;
}
System.out.println(sb);
}
public static void update(int index, long diff) {
while (index <= N) {
tree[index] += diff;
index += (index & -index);
}
}
static long sum(int index) {
long res = 0;
while (index > 0) {
res += tree[index];
index -= (index & -index);
}
return res;
}
}
Author And Source
이 문제에 관하여([1275]커피숍2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@away0419/1275커피숍2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)