[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;
	}

}

좋은 웹페이지 즐겨찾기