Recently I have to solve a problem like : given an array, update n times in range [Li..Ri] and then output the array .I updated them using segment tree and I found the array by querying indexes one by one. It took nlog(n). Can I do it in O(n) ? And additionally, can I find the condition of any index in O(1) ? Thanks in advance.