我已经阅读了一些关于两种常见数据结构的教程，它们可以在O(lg N)的时间内实现区间更新和查询：线段树和二叉索引树（BIT / Fenwick Tree）。
我找到的大多数示例都涉及到某些类似“范围内整数求和”、“范围内整数异或”等可交换和可结合运算。
我想知道这两个数据结构（或者任何其他数据结构/算法，请提议）是否可以在O(lg N)的时间内实现以下查询？（如果不行，那么O(sqrt N)呢）
给定一个整数数组A，在区间[l，r]中查询不同整数的数量
PS：假设可用整数的数量约为10^5，因此used [color] = true或位掩码不可能。
例如：A =[1,2,3,2,4,3,1]，query([2,5]) = 3，其中范围索引从0开始。
1 5 2 6 8 4 7 1是原始数组。|1 1 2 4 5 6 7 8|
|1 2 5 6|1 4 7 8|
|1 5|2 6|4 8|1 7|
|1|5|2|6|8|4|7|1|
a = 1 3 1 2 2 1 4 1
b = 3 ∞ 6 5 ∞ 8 ∞ ∞
有一种著名的离线方法可以解决这个问题。如果你有一个大小为n的数组和q个查询，在每个查询中，你需要知道该范围内不同数字的计数，那么你可以在O(n log n + q log n)的时间复杂度内解决整个问题。这类似于在O(log n)的时间内解决每个查询。
让我们使用RSQ（区间和查询）技术来解决这个问题。对于RSQ技术，您可以使用线段树或BIT。让我们讨论线段树技术。
要解决此问题，您需要一个离线技术和一个线段树。现在，什么是离线技术？？离线技术是在离线状态下执行某些操作。在问题求解中，离线技术的一个例子是，您首先输入所有查询，然后以一种方式重新排序它们，使您可以正确且轻松地回答它们，最后按给定的输入顺序输出答案。
解决思路：
首先，输入一个测试用例，并将给定的n个数字存储在数组中。假设数组名称为array []，并输入q个查询并将它们存储在向量v中。其中v的每个元素都包含三个字段-l，r，idx。其中l是查询的起点，r是查询的终点，而idx是查询的数量。例如：这是第n个查询。现在，根据查询的终点对向量v进行排序。假设我们有一个可以存储至少10 ^ 5个元素信息的线段树。我们还有一个名为last [100005]的数组，它存储数字在array []中的最后位置。
初始时，树的所有元素都为零，而上述所有元素均为-1。现在在数组[]上运行循环。现在，在循环内部，您需要检查每个数组[]索引的以下内容。
last [array [i]]是否为-1？如果是-1，则写入last [array [i]] = i，并调用update（）函数，该函数将在segment tree的last [array [i]] th位置加上+1。如果last [array [i]]不是-1，则调用segment tree的update（）函数，该函数将在segment tree的last [array [i]] th位置减去1或添加-1。现在，您需要将当前位置存储为将来的最后位置。因此，您需要编写last [array [i]] = i，并调用update（）函数，该函数将在segment tree的last [array [i]] th位置添加+1。
现在，您需要检查查询是否在当前索引完成。也就是说，如果（v [current]。r == i）。如果这是真的，那么调用segment tree的query（）函数，该函数将返回范围v [current]。l到v [current]。r和将结果存储在答案[]数组的v [current]。idx ^ th索引中。您还需要将当前值增加1。6.现在打印包含您最终答案的答案[]数组，按给定的输入顺序。
算法的复杂度为O（n log n）。
from bisect import bisect_left
import random
import time
def build_index(input):
n = len(input)
last = {}
next = []
for j in range(n):
i = n - j - 1
if input[i] in last:
next.append(last[input[i]])
else:
next.append(n)
last[input[i]] = i
next.reverse()
return next
def merge(left, right):
answer = []
p = 0
q = 0
while True:
if p == len(left):
if q == len(right):
return answer
else:
answer.append(right[q])
q += 1
elif q == len(right):
answer.append(left[p])
p += 1
elif left[p] < right[q]:
answer.append(left[p])
p += 1
else:
answer.append(right[q])
q += 1
def build_tree(input, l, r):
if r - l == 1:
return (input[l:r], None, None)
else:
mid = (l + r) // 2
left = build_tree(input, l, mid)
right = build_tree(input, mid, r)
merged = merge(left[0], right[0])
return (merged, left, right)
def query(index, tree_left, tree_right, query_l, query_r):
tree_width = tree_right - tree_left
if tree_width == 1:
if index[0][0] >= query_r:
return 1
else:
return 0
else:
mid = (tree_left + tree_right) // 2
if query_r <= mid:
return query(index[1], tree_left, mid, query_l, query_r)
elif query_l >= mid:
return query(index[2], mid, tree_right, query_l, query_r)
elif query_l <= tree_left and query_r >= tree_right:
arr = index[0]
return tree_width - bisect_left(arr, query_r)
else:
return query(index[1], tree_left, mid, query_l, query_r) + query(index[2], mid, tree_right, query_l, query_r)
def brute(input, i, j):
seen = {}
for k in range(i, j):
seen[input[k]] = True
return len(seen)
input = random.choices(list(range(8)), k=100000)
index = build_index(input)
tree = build_tree(index, 0, len(index))
n = len(input)
i = random.randint(0, n)
j = random.randint(i + 1, n)
t1 = time.time()
q = query(tree, 0, len(index), i, j)
t2 = time.time()
b = brute(input, i, j)
t3 = time.time()
print(q == b)
print(t2 - t1)
print(t3 - t2)
O(n)是下限，因为您需要查看每个元素。 - saschaO(r-l)。 - sascha