Does there any O(1) Solution exist for this Problem?

Question

We have been given an array of size N 1 <= N <= 1e5, with Ai positive integers, such that

1 <= Ai <= 1e9.

we will be given Q queries. 1 <= Q <= 1e5

Every time in a query there will be two space separated integers b c , 1 <= b,c <= N

For every query we need to find that Is moving from index b of array to index c of array possible ?, and if it is then we have find a special sum, which i have explained below.

We can't just move in array simply from i to i+1 index, there is a restriction. If we want to move from i to j then A[j] should be strictly greater than A[i], i.e A[j] > A[i].

Note here one thing that : While moving we have to take the just next greater element than the current.

The sum what we need to find is sum of elements that came in the path taken to reach destination.

For Example
array : 3 2 5 4 6 6 7
query : 1 7
So, according to query we need to move from 1st element to last element if possible.
As, we can see we can take 3 --> 5 --> 6 --> 7 path to reach the destination and sum is 3+5+6+7 = 21
But if last element in array was 2
array : 3 2 5 4 6 6 2
query : 1 7
For this query we cant reach to destination as after 6 the destination element 2 is smaller than it. So for this query NO answer exist.

My approach
I know i can find the answer in O(n), by traversing the array simply from A(b) to A(c) and finding out that if answer exit or not as well as sum.
But the Problem is that There are a lot of queries so if i use O(n) solution the Time Complexity will be O(QN).
Time limit is only 1 sec, So i need to find a constant time O(c)solution for this.

One Thing more The becomes even tougher when Queries of second type appear.

Query type 2: In this query we need to update the value at an index with a given K. query : b k , then A[b] = K.

Can anyone help me on this ??

Answer 1

The question is asking for N queries, the solution is most probably to do a pre-process to compute the possibilities and then query each of them in O(1) time.