By adyyy, history, 2 weeks ago,

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 .

• +2

 » 2 weeks ago, # |   0 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.
•  » » 2 weeks ago, # ^ |   0 is there any such problem , i dont know about how to apply segment tree here in this problem .
 » 2 weeks ago, # | ← Rev. 2 →   +14 I think we can solve it using Fenwick treeHere 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.
•  » » 2 weeks ago, # ^ |   0 yeah i think this is right apporach . thanks for helping buddy
•  » » 2 weeks ago, # ^ |   +5 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.