1081.cpp

#include <stdio.h>
#include <algorithm>
#include <vector>

typedef long long lld;

struct SegmentTree {
	std::vector<lld> data;

	void __build(const std::vector<int>& arr, int index, int left, int right) {
		if (left == right) {
			data[index] = arr[left];
			//printf("sum[%d, %d]=%lld\n", left, right, data[index]);
			return;
		}
		int mid = (left+right) >> 1;
		int lc = (index << 1) + 1;
		int rc = lc+1;
		__build(arr, lc, left, mid);
		__build(arr, rc, mid+1, right);
		data[index] = data[2*index+1] + data[2*index+2];
		//printf("sum[%d, %d]=%lld\n", left, right, data[index]);
	}

	lld __sum(int index, int left, int right, int need_left, int need_right) {
		if (need_left > need_right) {
			return 0;
		}

		if (left == need_left && right == need_right) {
			return data[index];
		}

		int mid = (left + right) >> 1;
		int lc = (index << 1) + 1;
		int rc = lc+1;
		return __sum(lc, left, mid, need_left, std::min(need_right, mid))+
			__sum(rc, mid+1, right, std::max(need_left, mid+1), need_right);
	}

	SegmentTree(const std::vector<int>& arr){
		int n = (int) arr.size();
		data.assign(4*n, 0);
		__build(arr, 0, 0, n-1);
	}

	lld sum(int left, int right) {
		int n = (int)data.size() / 4;
		return __sum(0, 0, n-1, left, right);
	}

};

int main() {
	freopen("input.txt", "rt", stdin);

	int n;
	scanf("%d", &n);

	std::vector<int> a(n);
	for (auto& it : a) {
		scanf("%d", &it);
		//printf("%d ", it);
	}
	//printf("\n");

	SegmentTree st(a);

	int m;
	scanf("%d", &m);


	std::vector<int> left(m), right(m);
	for (int i = 0; i < m; ++i) {
		scanf("%d %d", &left[i], &right[i]);
	}

	std::vector<lld> answers(m);
	for (int i = 0; i < m; ++i) {
		answers[i] = st.sum(left[i]-1, right[i]-1);
	}

	for (auto it:answers) {
		//printf("%lld ", it);
		printf("%I64d ", it);
	}

	return 0;
}