提问人：Tomek Swiecki 提问时间：9/5/2023 更新时间：9/7/2023 访问量：61
在动态数组中查找间隔中不同整数的数量
Find the number of different integers in an interval in a dynamic array
问：
给定一个长度为 N 和 Q 的整数数组 a[i] 查询。
1 <= N， Q <= 10^5 1 <= a[i] <= 10^6
有 2 种类型的查询。它们包括：
两个整数 l 和 r。处理完此查询后，您必须打印间隔 [l，r] 上不同整数的数量
两个整数 i 和 x。在此查询之后，将第 i 位处的值更改为 x。
我通过使用 sqrt（N） bool 表进行简单的 sqrt 分解并将两个查询的结果组合在 O（sqrt（N）） 中来完成这项任务。
不幸的是，这不起作用，因为我最多只能使用 512 MB，我使用了太多内存。有谁知道如何解决这个问题？
答：
0赞
Matt Timmermans
9/7/2023
#1
假设你有一个整数数组。
对于出现多次的每个整数，创建连接相邻实例的间隔。例如，如果 5 出现在位置 2、10 和 16，则得到区间 [2,10] 和 [10,16]。
现在，对于任何范围 [l，r]，请注意该范围内的出现次数和间隔数。如果 5 出现在范围内，则 number_of_occurrences - number_of_intervals = 1。如果没有，则为 0。
如果我们为数组中的所有整数创建间隔，那么我们可以使用它来计算范围内的不同整数。该范围内出现的整数数仅为 r-l+1。减去间隔总数，得到非重复整数的数目。
为了快速计算一个范围内的间隔总数，我们可以利用所有间隔具有不同起始位置的事实。 创建一个数组，该数组在每个间隔的开始位置包含相应的结束位置。现在，要查找 [l，r] 中的区间总数，您可以找到位置在 [l，r] 中为 <= r 的数字计数。
为了快速回答这些问题，请制作 log（N） 图层。在第一层中，我们将为每对元素制作一个阶次统计树。在下一层中，每 4 棵树一棵树，依此类推。然后，任何范围 [l，r] 都被 O（log N） 树完全覆盖，允许我们在 O（log2 N） 时间内回答查询。
实现这一点以便您可以在线进行更改并回答这些查询非常复杂。您需要跟踪 BST 中每个整数的出现次数，以便您可以快速更新间隔范围。不过，您可以在 O（N log2 N） 时间和 O（N log N） 空间内完成整个工作。
评论
[l, r][l, r]