Segment Tree Algorithm

The Segment Tree (Add-Min-Max) Algorithm is a versatile and efficient data structure that is used to solve various range query problems, especially when the underlying data is mutable. It is particularly useful in scenarios where one needs to quickly find the minimum, maximum, or sum of elements within a given range in an array, as well as perform updates to the array elements. The key idea behind the segment tree is to represent the array as a balanced binary tree, where each node stores the minimum, maximum, and sum of a specific subarray. The tree is designed in such a way that it can efficiently combine the results of its children nodes to compute the desired query for the parent node. To build the segment tree, the algorithm starts by recursively dividing the array into two equal halves until it reaches the individual elements, which form the leaf nodes of the tree. The internal nodes store the minimum, maximum, and sum of their corresponding subarrays. Once the tree is built, range queries and updates can be executed in logarithmic time complexity (O(log N)), where N is the number of elements in the array. The algorithm traverses the tree from the root node, checking whether the current node's range is entirely within, partially overlaps, or is disjoint with the query range. If the node's range is within the query range, the algorithm returns the minimum, maximum, and sum for that node; if it's disjoint, it returns a neutral value (e.g., infinity for minimum queries); and if it partially overlaps, the algorithm combines the results from its children nodes to compute the answer. Updates are performed by traversing the tree and updating the relevant nodes that cover the modified array element. Overall, the Segment Tree (Add-Min-Max) Algorithm is a powerful and flexible tool for solving a wide range of problems involving mutable arrays and range queries.
/*************************************************************************************

    Segment tree. Solves RMQ problem (maximum on a segment and value update)
    O(N) on precalculation, O(logN) on query.

    Based on problem 3309 from informatics.mccme.ru: 
    http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3309

*************************************************************************************/

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>

using namespace std;

const int MAXN = 105000;
const int INF = (int) 1e9;

int n, num, qn;
int a[MAXN];
int tree[4 * MAXN];
int l, r;

int getMax(int l, int r) {
    l = num + l - 1; r = num + r - 1;
    int res = -INF;
    
    while (l <= r) {
        if (l & 1) {
            res = max(res, tree[l]);
            l++;
        }
        if (r % 2 == 0) {
            res = max(res, tree[r]);
            r--;
        }
        l /= 2; r /= 2;
    }

    return res;
}

void update(int pos, int val) {
    pos = num + pos - 1;
    tree[pos] = val;
    pos /= 2;
    while (pos >= 1) {
        tree[pos] = max(tree[pos * 2], tree[pos * 2 + 1]);
        pos /= 2;
    }
}

int main() {
    //assert(freopen("input.txt","r",stdin));
    //assert(freopen("output.txt","w",stdout));

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    num = 1;
    while (num < n)
        num *= 2;

    for (int i = num; i < 2 * num; i++) {
        if (i - num + 1 <= n)
            tree[i] = a[i - num + 1];
        else
            tree[i] = -INF;
    }
    
    for (int i = num - 1; i >= 1; i--) {
        tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }

    scanf("%d", &qn);
    for (int i = 1; i <= qn; i++) {
        scanf("%d %d", &l, &r);
        printf("%d ", getMax(l, r));
    }

    return 0;
}

LANGUAGE:

DARK MODE: