algorithm - 数组给定范围内每个不同整数的出现次数

Question

给定一个包含 n 个整数的数组 (n <= 1e6) [a0, a1, a2, ... an-1] (a[i] <= 1e9)和多个查询。在每个查询中 2整数 l和 r (0 <= l <= r <= n-1)给出了，我们需要返回此范围内每个不同整数的计数(l 和 r 包括在内)。

我只能想出一个强力解决方案来遍历每个查询的完整范围。

d={}
for i in range(l, r+1):
    if arr[i] not in d:
        d[arr[i]]=0
    d[arr[i]]+=1

例如:

Array is [1, 1, 2, 3, 1, 2, 1]

Query 1: l=0, r=6, Output: 4, 2, 3 (4 for 4 1's, 2, for 2 2's and 1 for 1 3)
Query 2: l=3, r=5, Output: 1, 1, 1

编辑 - 我想出了类似的东西，但它的复杂性仍然很高。我认为是因为那个插入操作。

const ll N = 1e6+5;
ll arr[N];
unordered_map< ll, ll > tree[4 * N];
int n, q;

void build (ll node = 1, ll start = 1, ll end = n) {
    if (start == end) {
        tree[node][arr[start]] = 1;
        return;
    }
    ll mid = (start + end) / 2;
    build (2 * node, start, mid);
    build (2 * node + 1, mid + 1, end);
    for (auto& p : tree[2 * node]) {
        ll x = p.ff;
        ll y = p.ss;
        tree[node][x] += y;
    }
    for (auto& p : tree[2 * node + 1]) {
        ll x = p.ff;
        ll y = p.ss;
        tree[node][x] += y;
    }
}

vector< ll > query (ll node, ll l, ll r, ll start = 1, ll end = n) {
    vector< ll > ans;
    if (end < l or start > r) return ans;
    if (start >= l and end <= r) {
        for (auto p : tree[node]) {
            ans.push_back (p.ss);
        }
        return ans;
    }
    ll mid = (start + end) / 2;
    vector< ll > b = query (2 * node, l, r, start, mid);
    ans.insert (ans.end (), b.begin (), b.end ());
    b = query (2 * node + 1, l, r, mid + 1, end);
    ans.insert (ans.end (), b.begin (), b.end ());
    return ans;
}

Answer 1

您可以使用描述的二叉索引树 here .不是在节点中存储范围总和，而是存储从值到各个范围的计数的映射。

现在用输入 x 查询树，以找到表示相应索引前缀 [1..i] 中每个元素出现频率的映射。这将需要合并 O(log n) 个映射。

现在您可以执行两个查询:一个针对 l-1，另一个针对 r。从后者“减去”前者的结果图。 map 减法是按条目进行的。我会让你弄清楚细节。`

每个查询的时间为 O(k log n)，其中 k 是 map 大小。这最多是输入数组中不同元素的数量。