To complement ngoaho91's answer.
The best way to solve this problem is using the Segment Tree data structure. This allows you to answer such queries in O(log(n)), that would mean the total complexity of your algorithm would be O(Qlogn) where Q is the number of queries. If you used the naive algorithm, the total complexity would be O(Qn) which is obviouslly slower.
There is, however, a drawback of the usage of Segment Trees. It takes up a lot of memory, but a lot of times you care less about memory than about speed.
I will briefly describe the algorithms used by this DS:
The segment tree is just an special case of a Binary Search Tree, where every node holds the value of the range it is assigned to. The root node, is assigned the range [0, n]. The left child is assigned the range [0, (0+n)/2] and the right child [(0+n)/2+1, n]. This way the tree will be built.
Create Tree:
/*
A[] -> array of original values
tree[] -> Segment Tree Data Structure.
node -> the node we are actually in: remember left child is 2*node, right child is 2*node+1
a, b -> The limits of the actual array. This is used because we are dealing
with a recursive function.
*/
int tree[SIZE];
void build_tree(vector<int> A, int node, int a, int b) {
if (a == b) { // We get to a simple element
tree[node] = A[a]; // This node stores the only value
}
else {
int leftChild, rightChild, middle;
leftChild = 2*node;
rightChild = 2*node+1; // Or leftChild+1
middle = (a+b) / 2;
build_tree(A, leftChild, a, middle); // Recursively build the tree in the left child
build_tree(A, rightChild, middle+1, b); // Recursively build the tree in the right child
tree[node] = max(tree[leftChild], tree[rightChild]); // The Value of the actual node,
//is the max of both of the children.
}
}
Query Tree
int query(int node, int a, int b, int p, int q) {
if (b < p || a > q) // The actual range is outside this range
return -INF; // Return a negative big number. Can you figure out why?
else if (p >= a && b >= q) // Query inside the range
return tree[node];
int l, r, m;
l = 2*node;
r = l+1;
m = (a+b) / 2;
return max(query(l, a, m, p, q), query(r, m+1, b, p, q)); // Return the max of querying both children.
}
If you need further explanation, just let me know.
BTW, Segment Tree also supports update of a single element or a range of elements in O(log n)