×

FNCS - Editorial

Author: Devendra Agarwal

Tester: Sergey Kulik

Editorialist: Florin Chirica

medium-hard

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.

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
To be updated soon

This question is marked "community wiki".

3★elfus ♦♦
0112527
accept rate: 0%

19.7k350498541

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 pre-computation 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).

(17 Nov '14, 19:33)

 1 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 5●1●1●1 accept rate: 0%
 0 I wrote a solution which takes O(n) time to update and O(1) time to query but it was giving TLE for the last 2 subtasks. Can anyone help me understand why it was giving TLE? answered 17 Nov '14, 20:01 9 accept rate: 0% 1 ≤ Q,N ≤ 10^5. Worst case O(Q * N). Let's say half of the queries are update queries. Then you would already have around 5 * 10^9 operations. That's not something your computer can do in 2.5 seconds. (20 Nov '14, 01:52) samjay5★
 0 I am getting forbidden error when I try to see setters solution. Looks like I am missing something answered 17 Nov '14, 23:06 1 accept rate: 0%
 0 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 3★evandrix 165●1●4●8 accept rate: 0%
 0 nishantkumars ...linear time complexity is too much for update operation..u need to reduce the complexity.. answered 17 Nov '14, 23:44 100●9 accept rate: 5%
 0 I'm wondering is there someone who user the limitation in subtask 2 where R - L <= 10? It would help me if n - m <= 100 for example, but I had no idea how to use the one mentioned above... answered 18 Nov '14, 06:45 16.9k●49●115●225 accept rate: 11% 1 yes, just keep a segment tree for the value of all functions so that you can query the sum of functions [m,n]. Also store the index of all functions starting from any given index in the original array. On updating index x, you only need to update the functions that start from either x-1,x-2....,x-10 and ending at or after x. There can be O(n) such functions for a given x, but since x is unique total complexity will stay qlogn. (18 Nov '14, 12:04) Great, thanks for an answer, I misunderstood the x will be distinct part, I thought elements in A are distinct and it didn't help me, suprisingly :-D (18 Nov '14, 12:35) 1 Although I didn't use 'all x are distinct' constraint, I used the R-L<=10 part to keep a vector of vectors where vector[i] stores occurrences of index i in the intervals array. Then I divided the queries into square root(q) segments and for each segment, I applied brute force. For all queries of type 2 in a segment, I iterated over all queries of type 1 before it and checked which queries of type 1 affect the current type 2 query. For this, I binary searched in the vector[i] part of the index x of type 1 query to find no. of occurrences of this index in range [m,n] of type 2 query. (19 Nov '14, 13:59) I feel that, if x are not distinct it won't fit, I need to think more abouot this. Thanks for you answer ;-) (19 Nov '14, 14:50) Yeah you're right about the distinct x part. Used it without knowing it! (19 Nov '14, 18:58)
 0 "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 3★nil96 180●7●18●45 accept rate: 5%
 0 Please explain in detail cant get your solution?? answered 24 Nov '14, 09:30 3★nil96 180●7●18●45 accept rate: 5%
 0 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 126●1●2●8 accept rate: 15%
 0 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 1 accept rate: 0%
 0 Can someone, please, post the test data for Task #2 (i.e. first test of the Sub-Task3)? 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 5★mattioli 1 accept rate: 0%
 0 you can solve this problem with sqrt-decomposition on queries + persistent segment tree :) My solution: https://www.codechef.com/viewsolution/17543787 answered 26 Feb '18, 03:35 4★nunes 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,727
×1,385
×1,237
×288
×179
×146

question asked: 17 Nov '14, 18:53

question was seen: 9,104 times

last updated: 26 Feb '18, 03:35