algorithm - CSES范围查询问题: Salary Queries

Question

我正在尝试解决这个问题:https://cses.fi/problemset/task/1144/
给定一个最多为 200000 的数组元素，我的任务是最多处理 200000查询，要么让我更新数组中的单个值，要么让我找到给定范围内 a 和 b 之间的元素数量(例如，查询会询问从索引 1 到5 位于 [2, 3] 范围内)。
我目前的想法是首先对给定数组中的值使用索引压缩(因为值可以达到 10^9 ，所以保留一个简单的出现数组会超出存储限制)，然后保留另一个包含出现次数的数组每个压缩的数字。然后，可以使用求和段树来处理和更新查询。
但是，我在尝试实现这种方法时遇到了问题。我意识到更新单个数组值会迫使我更改压缩数组。
例如，给定一个数组 [1, 5, 3, 3, 2] ，我会定义一个压缩函数 C以至于

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

然后，出现数组将是 [1, 1, 2, 1] ，并且处理总和查询将是有效的。但是，如果我被指示更新一个值，比如说，将第三个元素更改为 4 ，那么这会使一切失去平衡。压缩功能必须更改为

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

这将迫使我重建我的事件数组，导致 O(N)更新时间。
自 N可达200000 ，我目前的方法不能有效地解决问题，尽管我认为我对索引压缩有正确的想法。有人可以用我的方法指出我正确的方向吗？

Answer 1

您在使用索引压缩方面有正确的想法 - 很棒的想法!如 N最多只有200000 , 保持一个出现数组最多需要 200000给定数组的初始值的元素，而不是 10^9数组索引。
根据您自己的说法，您面临的问题是在处理查询过程中遇到新值时。你是对的;这将使发生数组失去平衡并导致更新必须在 O(N) 中运行。时间。此问题的解决方案只是对您当前方法的微小修改。
为了解决遇到新值的问题，我们可以确保永远不会遇到任何新值。我们可以通过在构造求和段树之前读入所有查询来做到这一点。这将导致最大 N + 2*Q唯一值，或 600000在最坏的情况下，这足以构造一个具有问题的 512MB 存储限制的发生数组。之后，求和段树将能够有效地回答这些查询。
所以最终解决这个问题的策略是输入每个唯一的数字，然后构造一个索引压缩函数，然后使用求和段树来有效地处理求和查询。
将来，请记住，在此类查询-回答问题中，在预计算之前读取所有输入可能会很有用。祝你的程序好运。