1
$\begingroup$

I'm trying to solve this problem: https://cses.fi/problemset/task/1144/

Given an array of up to 200000 elements, my task is to process up to 200000 queries, which either ask me to update a single value within the array or ask me to find the number of elements that lie in a given range.

My current idea is to first use index compression on the given array, then keep another array that contains the number of occurrences of each number. Then, processing and updating queries could be done using a sum segment tree.

However, I ran into a problem while trying to implement this approach. I realized that updating a single array value could force me to shift the compressed array.

For example, given an array [1, 5, 3, 3, 2], I would define a compression function C such that

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;

Then, the occurrence array would be [1, 1, 2, 1], and processing sum queries would be efficient. However, if I were instructed to update a value, say, change the third element to 4, then that throws everything out of balance. The compression function would have to change to

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;

which would force me to reconstruct my occurrence array, resulting in O(N) update time.

Since N can be up to 200000, my approach will not work efficiently enough to solve the problem, although I think I have the right idea with index compression. Can somebody please point me in the right direction?

$\endgroup$
7
  • 1
    $\begingroup$ Are you solving problems on the CSES problem set? (I remember seeing you ask another Range Query Question a while back.) If so, you should try searching for hints/solutions online. I think several people have posted their solutions on GitHub. $\endgroup$
    – Telescope
    Aug 17, 2020 at 16:16
  • 1
    $\begingroup$ Yep, I am doing the CSES Problem Set! I always try to find solutions online before asking on a Stack Exchange website, but all the solution sets I've been able to find don't come with any explanation (and the code isn't readable...). $\endgroup$ Aug 17, 2020 at 16:17
  • $\begingroup$ If your numbers are integers, then you can use lazy segment trees: the segment tree covers the entire set of integers, and you construct nodes only when needed. I think this is the one: cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-13 $\endgroup$
    – user114966
    Aug 17, 2020 at 16:31
  • 1
    $\begingroup$ Can you credit the original source of this task in the question? That might help others understand the task, and help others with a similar question find this page via search. $\endgroup$
    – D.W.
    Aug 17, 2020 at 17:19
  • $\begingroup$ Good idea. My post now reflects that. $\endgroup$ Aug 17, 2020 at 18:01

0

Browse other questions tagged or ask your own question.