Hi, if there is a problem such that we are given an array of size (1<=n<=1e5) and queries (1<=q<=1e5) , int each query we are given a range [L,R] and we have to tell that if the array is increasing in that range or not . Also if we had a query for point update can this be solved ???? I was solving https://www.codechef.com/problems/DELSORT this problem so just thought about this question . I dont know if similar question already exists , if it does please provide link . Thanks .
Yes, this is solvable: the queries are equivalent to "is $$$[l, r - 1]$$$ in the difference array all-positive" which can be solved using a segment tree. The point updates don't break this solution either: a point update only changes 2 elements of the difference array so you can do 2 point updates in the constructed segment tree.
is there any such problem , i dont know about how to apply segment tree here in this problem .
I think we can solve it using Fenwick tree
Here is my solution -->
Traverse the array and check if(A[i]>A[i-1]) then update value for i to be 1 using update operation other wise keep it 0.
for the subarray(l,r) to be increasing sum(r) — sum(l) == r-l; (NOTE: we have take l not l-1)
for point update just check it with its neighbouring elements and update accordingly.
yeah i think this is right apporach . thanks for helping buddy
I have a slightly easier way with a Segtree:
We can check that $$$a_{i-1} < a_i$$$ for $$$1 \leq i < N$$$ (0-based indexing), and use the bitwise AND to check a subarray.
For the updates. we can simply check the elements around the update, and fix them accordingly, like you and -is-this-fft- explained.