Ant*_*ith 8 algorithm data-structures segment-tree range-query
我正在尝试解决这个问题：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，我目前的方法不能有效地解决问题，尽管我认为我对索引压缩有正确的想法。有人可以用我的方法指出我正确的方向吗？
您使用索引压缩的想法是正确的 - 很棒的想法！由于N仅达200000，保持发生阵列将至多需要200000，而不是对于给定的阵列的初始值的元素，10^9阵列索引。
根据您自己的说法，您面临的问题是在处理查询过程中遇到新值时。你是对的; 这会使发生数组失去平衡并导致更新必须及时运行O(N)。此问题的解决方案只是对您当前方法的微小修改。
为了解决遇到新值的问题，我们可以确保永远不会遇到任何新值。我们可以通过在构造求和段树之前读入所有查询来做到这一点。这将导致最大的N + 2*Q唯一值，或者600000在最坏的情况下，这足以构建一个具有问题的 512MB 存储限制的发生数组。之后，求和段树将能够有效地回答这些查询。
所以最终解决这个问题的策略是输入每个唯一的数字，然后构造一个索引压缩函数，然后使用求和段树来有效地处理求和查询。
将来，请记住，在此类查询-回答问题中，在 precomputation 之前读取所有输入可能会很有用。祝你的程序好运。