[백준 1275] 커피숍2

package javaSana.Day0917.segmentTree;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B_1275 {

	static int N, Q;
	static long[] arr, tree;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());

		arr = new long[N + 1];

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}

		tree = new long[N * 4];
		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());

			int minN = Math.min(x, y);
			int maxN = Math.max(x, y);
			
			System.out.println(sum(1, N, 1, minN, maxN));
			
			long dif = b - arr[a];
			arr[a] = b;
			
			update(1, N, 1, a, dif);
		}

	}

	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 idx, long dif) {
		if (idx < start || end < idx)
			return;

		tree[node] += dif;
		if (start == end)
			return;

		int mid = (start + end) / 2;
		update(start, mid, node * 2, idx, dif);
		update(mid + 1, end, node * 2 + 1, idx, dif);

	}

	static long sum(int start, int end, int node, int left, int right) {
		if (right < start || end < left) {
			return 0;
		}
		if (left <= start && end <= right) {
			return tree[node];
		}

		int mid = (start + end) / 2;
		return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
	}

}