public class Segtree {
	static int[] total = new int[400000];
	static int[] left = new int[400000], right = new int[400000];
	static int[] data;

	static void build(int l, int r, int node) {
		left[node] = l;
		right[node] = r;
		if (l + 1 == r) {
			total[node] = data[l];
			return;
		}
		int mid = (l + r) / 2;
		build(l, mid, node * 2);
		build(mid, r, node * 2 + 1);

		total[node] = total[node * 2] + total[node * 2 + 1];
	}

	static int query(int l, int r, int node) {
		// if current node is not inside interval
		if (left[node] >= r || right[node] <= l) {
			return 0;
		}
		// if current node is completely inside interval
		if (left[node] >= l && right[node] <= r) {
			return total[node];
		}
		// part of the thing
		return query(l, r, node * 2) + query(l, r, node * 2 + 1);
	}

	static void update(int position, int value, int node) {
		// updated position is not inside current segment
		if (left[node] > position || right[node] <= position) {
			return;
		}

		// is size 1
		if (left[node] + 1 == right[node]) {
			total[node] += value;
			return;
		}

		// check children
		update(position, value, node * 2);
		update(position, value, node * 2 + 1);

		// update itself
		total[node] = total[node * 2] + total[node * 2 + 1];
	}

	public static void main(String[] args) {
		data = new int[] { 3, 2, 4, 1, 2, 7, 8, 5 };
		build(0, 8, 1);
		System.out.println(query(1, 6, 1));
		update(2, 10, 1);
		System.out.println(query(1, 5, 1));
	}
}