Introducción al árbol de segmentos

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100010;

int n, q;
ll arr[MAXN];
ll segtree[MAXN << 2];
ll lazy[MAXN << 2];

void pushUp(int nodo) {
    segtree[nodo] = segtree[nodo << 1] + segtree[(nodo << 1) | 1];
}

void construir(int l, int r, int nodo) {
    lazy[nodo] = 0;
    if (l == r) {
        segtree[nodo] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    construir(l, mid, nodo << 1);
    construir(mid + 1, r, (nodo << 1) | 1);
    pushUp(nodo);
}

void aplicarLazy(int nodo, int longitud) {
    if (lazy[nodo] != 0) {
        int izq = nodo << 1;
        int der = (nodo << 1) | 1;
        lazy[izq] += lazy[nodo];
        lazy[der] += lazy[nodo];
        segtree[izq] += lazy[nodo] * (longitud - (longitud >> 1));
        segtree[der] += lazy[nodo] * (longitud >> 1);
        lazy[nodo] = 0;
    }
}

void actualizar(int ql, int qr, ll valor, int l, int r, int nodo) {
    if (ql <= l && r <= qr) {
        lazy[nodo] += valor;
        segtree[nodo] += valor * (r - l + 1);
        return;
    }
    aplicarLazy(nodo, r - l + 1);
    int mid = (l + r) >> 1;
    if (ql <= mid) actualizar(ql, qr, valor, l, mid, nodo << 1);
    if (qr > mid) actualizar(ql, qr, valor, mid + 1, r, (nodo << 1) | 1);
    pushUp(nodo);
}

ll consultar(int ql, int qr, int l, int r, int nodo) {
    if (ql <= l && r <= qr) {
        return segtree[nodo];
    }
    aplicarLazy(nodo, r - l + 1);
    int mid = (l + r) >> 1;
    ll res = 0;
    if (ql <= mid) res += consultar(ql, qr, l, mid, nodo << 1);
    if (qr > mid) res += consultar(ql, qr, mid + 1, r, (nodo << 1) | 1);
    return res;
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]);
    construir(1, n, 1);
    while (q--) {
        int tipo, x, y;
        ll z;
        scanf("%d", &tipo);
        if (tipo == 1) {
            scanf("%d %d %lld", &x, &y, &z);
            actualizar(x, y, z, 1, n, 1);
        } else {
            scanf("%d %d", &x, &y);
            printf("%lld\n", consultar(x, y, 1, n, 1));
        }
    }
    return 0;
}

Búsqueda del valor máximo en un intervalo

Entrada:
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

Salida:
9 9 7 7 9 8 7 9

Implementación con arreglos estáticos:

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100010;

int n, m;
int arr[MAXN];
int seg[MAXN << 2];

void pushUp(int nodo) {
    seg[nodo] = max(seg[nodo << 1], seg[(nodo << 1) | 1]);
}

void construir(int l, int r, int nodo) {
    if (l == r) {
        seg[nodo] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    construir(l, mid, nodo << 1);
    construir(mid + 1, r, (nodo << 1) | 1);
    pushUp(nodo);
}

int consultar(int ql, int qr, int l, int r, int nodo) {
    if (ql <= l && r <= qr) {
        return seg[nodo];
    }
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid) res = consultar(ql, qr, l, mid, nodo << 1);
    if (qr > mid) res = max(res, consultar(ql, qr, mid + 1, r, (nodo << 1) | 1));
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
    construir(1, n, 1);
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", consultar(a, b, 1, n, 1));
    }
    return 0;
}

Versión con punteros (evita desbordamiento de memoria):

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100010;

struct Nodo {
    int l, r;
    int maximo;
    Nodo *izq, *der;
    Nodo() : l(0), r(0), maximo(0), izq(nullptr), der(nullptr) {}
};

int arr[MAXN];
int n, m;

void pushUp(Nodo *nodo) {
    nodo->maximo = max(nodo->izq->maximo, nodo->der->maximo);
}

void construir(int l, int r, Nodo *nodo) {
    nodo->l = l;
    nodo->r = r;
    if (l == r) {
        nodo->maximo = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    if (!nodo->izq) nodo->izq = new Nodo();
    if (!nodo->der) nodo->der = new Nodo();
    construir(l, mid, nodo->izq);
    construir(mid + 1, r, nodo->der);
    pushUp(nodo);
}

int consultar(Nodo *nodo, int ql, int qr) {
    if (!nodo) return 0;
    if (ql <= nodo->l && nodo->r <= qr) {
        return nodo->maximo;
    }
    int mid = (nodo->l + nodo->r) >> 1;
    int res = 0;
    if (ql <= mid) res = consultar(nodo->izq, ql, qr);
    if (qr > mid) res = max(res, consultar(nodo->der, ql, qr));
    return res;
}

int main() {
    Nodo *raiz = new Nodo();
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
    construir(1, n, raiz);
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", consultar(raiz, a, b));
    }
    return 0;
}

La implementación con punteros requiere cuidado al escribir, pero evita el riesgo de desbordamiento de memoria (MLE) inherente a los arreglos estáticos de gran tamaño.