Segment tree

#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pl;
typedef pair <ld, ld> pd;

const ll N = 1e6 + 100;
const ll P = 1e9 + 7;
const ll  M = 1e4 + 10;
const ld pi = acos(-1);
const ll INF = 1e18;

#define x first
#define y second
#define pb push_back

vector <ll> v;

struct node
{
	ll left, right, max, sum = 0, add = 0;
	node *child_left, *child_right;
};

node* build(ll left, ll right, vector <ll> &v) //строим дерево отрезков
{
	if (left > right)
		return NULL;

	node *res = new node;
	res->left = left,
	res->right = right;

	if (left == right)
	{
		res->child_left = NULL;
		res->child_right = NULL;
		res->sum = v[left];
		res->max = v[left];
	}
	else
	{
		ll mid = (left + right) / 2;
		res->child_left = build(left, mid, v);
		res->child_right = build(mid + 1, right, v);
		res->sum = res->child_left->sum + res->child_right->sum;
		res->max = max(res->child_left->max, res->child_right->max);
	}
	return res;
}

ll query_sum(node *root, ll left, ll right) // ищем сумму на отрезке [L;R]
{
	if (right < root->left || left > root->right)
		return 0;

	if (left <= root->left && right >= root->right)
		return root->sum + root->add;

	ll ans1 = query_sum(root->child_left, left, right),
	   ans2 = query_sum(root->child_right, left, right);

	return root->add + ans1 + ans2;
}

ll query_max(node *root, ll left, ll right) // ищем максимум на отрезке [L;R]
{
	if (right < root->left || left > root->right)
		return -INF;

	if (left <= root->left && right >= root->right)
		return root->max + root->add;

	ll ans1 = query_max(root->child_left, left, right);
	ll ans2 = query_max(root->child_right, left, right);

	return root->add + max(ans1, ans2);
}

void update(node *root, ll ind, ll x) //помещаем в элемент под индексом ind значение x
{
	if (ind < root->left || ind > root->right)
		return;

	if (root->left == root->right)
	{
		root->sum = x;
		root->max = x;
		return;
	}

	update(root->child_left, ind, x);
	update(root->child_right, ind, x);
	root->sum = root->child_left->sum + root->child_right->sum;
	root->max = max(root->child_left->max, root->child_right->max);
}

void update_on_segment(node *root, ll left, ll right, ll delta) //прибавляем какое-то delta к элементам [L;R]
{
	if (right < root->left || left > root->right)
		return;

	if (left <= root->left && right >= root->right)
		root->add += delta;
	else
	{
		update_on_segment(root->child_left, left, right, delta);
		update_on_segment(root->child_right, left, right, delta);

		root->sum = root->child_left->sum + root->child_left->add +
					root->child_right->sum + root->child_right->add;

		root->max = max(root->child_left->max + root->child_left->add,
			        root->child_right->max + root->child_right->add);
	}

}
int main()
{
	ll n;
	cin >> n;

	v.resize(n);

	for (ll i = 0; i < n; i++)
		cin >> v[i];

	node *root = build(0, n - 1, v);

	ll m;
	cin >> m;

	for (ll i = 0; i < m; i++)
	{
		ll left, right;
		cin >> left >> right;
		left--, right--;

		cout << query_max(root, left, right) << " ";
	}
    return 0;
}