PROBLEM LINK:Author: Devendra Agarwal Tester: Sergey Kulik Editorialist: Florin Chirica DIFFICULTY:mediumhard PREREQUISITES:sqrt decompositions, Fenwick Trees (or Interval Trees). PROBLEM:You're given an array, which can modify in time. You're given some functions which return sum of some contiguous subsequence (subarray). Answer queries, which ask sum of a contiguous subsequence of functions. QUICK EXPLANATION (thanks to Sunny Aggarwal):In the begining, we can find the value of every function and thus we can easily find the sum of functions of every chunk in the beginning easily. Now we need to take care for updating. For updating, we need in O(1) time for each chunk that how many time x comes in summation of the functions in that chunk. We can precompute this factor in O(N*sqrt(N)) space and time. Thus, we can update this structure in O(sqrt(N)) by traversing through all the chunks and applying +(yfactor)(prevfactor) at every chunk. We will quickly travel between 2 points which has full chunks. Only thing to worry is with partial chunks. We can use BIT's to achieve this in O( sqrt(N)*log(N) ). EXPLANATION:Complexity of the official solution This looks like a weird start, isn't it? Well, actually the idea is that you might try to find a complexity better than needed. Our solution uses O(log(n) * sqrt(n)) per update and O(sqrt(n)) per query. If you're trying to find a better complexity, this might be a hint to look for this complexity, as it passes the systests. If you have a solution with better complexity, please share it with us in the comments! Smart brute force A brute force solution would be at following: do an update in O(1) and query by iterating over all functions from m to n and for each function iterate all elements from L to R. This gives a running time of O(n ^ 2) per query worst case... not good. An optimization might be pretty obvious for those who know Segment Tree / Fenwick Tree. We keep iterating all functions from m to n. But, for a function i, we can avoid calculating it in O(n) worst case. A function f(i) asks you for a sum of a range. Also, updates change a single element. Both Fenwick Trees and Segment Trees allow changing an element and asking for a sum in O(log(n)) time. So, for an update, using this technique, we can get O(log(n)) time and for a query we can get O(n * log(n))... still not good enough. No updates version Suppose we have no updates  then we can precalculate some information. In this way, a query can be answered faster. A well know trick is used: sqrt decomposition. If you don't know it, please read it from here. We keep L "buckets" of length L (L = sqrt(n)). First bucket will contain sum of 1st, 2nd, ..., Lth functions. Second bucket will contain sum of (L+1)th, (L+2)th, ..., (2*L)th functions and so on. As showed in the link, when we're given a query, we can iterate over "full blocks". These values are already calculated. Also, there can be at most 2 "incomplete blocks". For functions in incomplete blocks, but which are in query range, we need to calculate the values of the functions using the Fenwick tree. This way we get O(log(n)) per update and O(log(n) * sqrt(n)) per query. Full version What happens when a position gets a new value? Firstly, we need to update Fenwick tree (or Segment tree). This will help for having the correct values when iterating elements in incomplete blocks. Suppose previous value was prev and my new value is val. We need to iterate each "complete" bucket. Suppose for a bucket we know how many functions from it contain position pos. Formally, we need to count functions f(i) from a bucket such as L[i] <= pos <= R[i]. For all those functions, we'll have to erase prev and add val. Let's denote number of functions from bucket which contain position pos by x. Then, it can be showed that bucket's value is modified by adding x * (val  prev) (for each function which contains position pos, we remove prev and add val, in total whole bucket modifies by x * (val  prev) ). It remains a single detail to handle: we need to know, for each position and for each bucket, how many functions from that bucket contain that position (value x from above). Let's define matrix x[bucket][pos] = how many functions from the bucket contain position pos. How to do this in a reasonable time? Let's iterate over all buckets. Suppose we're solving now bucket B. It will contain some functions which say: f(x0, y0) = all positions between x0 and y0 appear one more time in the bucket B. So, we need to increase x[B][x0], x[B][x0 + 1], ..., x[B][y0  1], x[B][y0] by 1. If the increase is done in O(1) time plus O(n) at final, complexity becomes O(n * sqrt(n)). How do to this? The problem reduced to: given M queries of form (x0, y0), increase all elements from all positions from x0 to y0 by 1. The solution is well known. We keep two arrays: A and B. When you get an operation x0, y0, you do: A[x0] += 1; A[y0 + 1] = 1; Then, you do B[i] = A[0] + A 1 + ... + A[i] = A[i] + B[i  1]. The correct answers will be in array B. We leave as an exercise to proof why this works. This problem allows multiple solutions. If you have alternative solutions, please share them with us in the comment section! AUTHOR'S AND TESTER'S SOLUTIONS:To be updated soon
This question is marked "community wiki".
asked 17 Nov '14, 18:53

I can solve it with complexity O(sqrt(max(N,Q))) per query and O(sqrt(max(N,Q))) per update. We split all the operations we must perform in sqrt(Q) groups. We solve each group separately. Before starting with the current group we go through all update queries which happened before the group and update the array (in reality  just the updates in the previous group; others have already been counted). Then we extract all numbers which we will need to update in the current group and put 0 in their place in the array (there are at most sqrt(Q) such numbers). Then we answer all the queries in the group without looking at the updates in the group (this can be done in constant time per query if we precompute arrays with preffix sums). What is left is the ammount updates in our group give. We transform each query [L,R] into two queries [0,R] and [0,L1]. We go through the sum intervals from left to right. When we are at interval P we will answer queries [0,P]. Assume we have an array which can add number to interval in O(sqrt(N)) and get value at some index in O(1). So, for each sum interval (from left to right) we can add 1 to it and now when we are at interval P we will know how many intervals cover each number ( = how many times we must add the number to the query result). The remaining is simple  just go through all the numbers affected by updates in our group (which are at most sqrt(Q)) and add them with the correct count from the array above. Array which can add number to interval in O(sqrt(N)) and get value at index in O(1) again is done with sqrtdecomposition. I guess it won't be very usefull, but here is my solution  http://www.codechef.com/viewsolution/5351179 answered 19 Nov '14, 14:42

As for authur's solution,I wonder what the i is ? if it is the index of the bucket,how can we know occurrences of pos in range [1,x] , considering the array B is just one dimension,but you must deal with the pos and the x.I need HELP!!! answered 19 Nov '14, 20:34

I am getting forbidden error when I try to see setters solution. Looks like I am missing something answered 17 Nov '14, 23:06

The message "Access Denied" is displayed to me when I try to view the Author and Tester's solutions linked. Please fix? answered 17 Nov '14, 23:14

nishantkumars ...linear time complexity is too much for update operation..u need to reduce the complexity.. answered 17 Nov '14, 23:44

"We can precompute this factor in O(N*sqrt(N)) space and time. Thus, we can update this structure in O(sqrt(N)) by traversing through all the chunks and applying +(yfactor)(prevfactor) at every chunk" what does this mean???please someone elaborate this answered 24 Nov '14, 09:04

Please explain in detail cant get your solution?? answered 24 Nov '14, 09:30

As we are undating only blocks .....how would we get correct sum in case of incomplete block since we are not updating the actual functions with the given index ??? please explain..... answered 02 Dec '14, 02:12

Can you please elaborate on "No update version"? I am unable to understand the use of segment tree in that.
link
This answer is marked "community wiki".
answered 04 Jul '15, 17:06

Can someone, please, post the test data for Task #2 (i.e. first test of the SubTask3)? This is the only test that I'm receiving WA. I've already tried many, many things and many, many random tests but I'm not able to find my mistake... I would really appreciate this specific test. Thanks a lot. answered 22 Mar '17, 07:47

you can solve this problem with sqrtdecomposition on queries + persistent segment tree :) My solution: https://www.codechef.com/viewsolution/17543787 answered 26 Feb '18, 03:35

i tried an O(q log(n)sqrt(q)) solution that i couldn't get to run in time. To know how many times a particular x occurs in range of functions [m,n], i used a persistent segment tree with precomputation nlogn . After every sqrt(q) queries i updated my prefix sum array.For each query i just visited all the updates within that chunk of queries. So, query was O(sqrt(q)log(n)) , while update was O(1).