码风进行了一定的统一

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 50005
#define DEPTH 25
#define int long long

int n, q;
int a[N];
int tree[DEPTH][N], sum[DEPTH][N];
int maxn, leaf[N << 2], depth[N << 2];

void build(int k, int l, int r, int dep)
{
	int *Tree = tree[dep], *Sum = sum[dep];

	if (l == r)
	{
		Tree[l] = Sum[l] = a[l];
		leaf[l] = k;
		return;
	}

	int mid = l + r >> 1;

	Sum[mid] = Tree[mid] = a[mid];
	int sums = a[mid], mins = min(a[mid], 0ll);
	for (int i = mid - 1; i >= l; --i)
		sums += a[i],
			Sum[i] = max(Sum[i + 1], sums),
			Tree[i] = max(Tree[i + 1], sums - mins),
			mins = min(mins, sums);

	Sum[mid + 1] = Tree[mid + 1] = a[mid + 1];
	sums = a[mid + 1], mins = min(a[mid + 1], 0ll);
	for (int i = mid + 2; i <= r; ++i)
		sums += a[i],
			Sum[i] = max(Sum[i - 1], sums),
			Tree[i] = max(Tree[i - 1], sums - mins),
			mins = min(mins, sums);

	build(k << 1, l, mid, dep + 1);
	build(k << 1 | 1, mid + 1, r, dep + 1);
}

int query(int l, int r)
{
	if (l == r)
		return a[l];
	int dep = depth[leaf[l]] - depth[leaf[l] ^ leaf[r]];
	int *Tree = tree[dep], *Sum = sum[dep];
	return max(max(Tree[l], Tree[r]), Sum[l] + Sum[r]);
}

signed main()
{
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%lld", &a[i]);

	for (maxn = 1; maxn < n; maxn <<= 1)
		;
	for (int i = 2; i <= 1 << maxn; ++i)
		depth[i] = depth[i >> 1] + 1;
	build(1, 1, maxn, 1);

	scanf("%lld", &q);
	while (q--)
	{
		int l, r;
		scanf("%lld%lld", &l, &r);
		printf("%lld\n", query(l, r));
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
	int x = 0, fh = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-')
			fh = -1;
	for (; isdigit(ch); ch = getchar())
		x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * fh;
}

inline void Out(int x)
{
	static char sta[18], top, flag = false;
	if (!x)
	{
		puts("0");
		return;
	}
	sta[top = 1] = '\n';
	if (x < 0)
		flag = true, x = -x;
	for (; x; x /= 10)
		sta[++top] = (x % 10) + 48;
	if (flag)
		putchar('-'), flag = false;
	while (top)
		putchar(sta[top--]);
}

const int N = 50100, Maxn = N * 4, MaxLog = 20, inf = 0x7f7f7f7f;

int n;
int pos[Maxn], val[Maxn], Log2[Maxn], maxlen;
inline int Max(int a, int b) { return a > b ? a : b; }

int Pre[MaxLog][Maxn], Sum[MaxLog][Maxn];

void Build(int o, int l, int r, int dep)
{
	int *Sumt = Sum[dep], *Pret = Pre[dep];
	if (l == r)
	{
		pos[l] = o;
		return;
	}
	int mid = (l + r) >> 1, sum, minv;

	Sumt[mid] = Pret[mid] = sum = minv = val[mid];
	minv = min(minv, 0);
	for (register int i = (mid - 1), iend = (int)(l); i >= iend; --i)
	{
		Pret[i] = Max(Pret[i + 1], sum += val[i]);
		Sumt[i] = Max(Sumt[i + 1], sum - minv);
		minv = min(minv, sum);
	}

	Sumt[mid + 1] = Pret[mid + 1] = sum = minv = val[mid + 1];
	minv = min(minv, 0);
	for (register int i = (mid + 2), iend = (int)(r); i <= iend; ++i)
	{
		Pret[i] = Max(Pret[i - 1], sum += val[i]);
		Sumt[i] = Max(Sumt[i - 1], sum - minv);
		minv = min(minv, sum);
	}

	Build(o << 1, l, mid, dep + 1);
	Build(o << 1 | 1, mid + 1, r, dep + 1);
}

int Query(int l, int r)
{
	if (l == r)
		return val[l];
	int dep = Log2[pos[l]] - Log2[pos[l] ^ pos[r]];
	int *Sumt = Sum[dep], *Pret = Pre[dep];
	return Max(Max(Sumt[l], Sumt[r]), Pret[l] + Pret[r]);
}

int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
		val[i] = read();

	for (maxlen = 1; maxlen < n; maxlen <<= 1)
		;
	Build(1, 1, maxlen, 1);

	for (int i = 2; i <= maxlen << 1; ++i)
		Log2[i] = Log2[i >> 1] + 1;

	int m = read();
	while (m--)
	{
		int l, r;
		l = read(), r = read();
		Out(Query(l, r));
	}
	return 0;
}