Calculating array segment uniformity using a segment tree

Question

You have to analyze some array of \$n\$ numbers. In particular, you are interested in the so-called array uniformity. Suppose that in the array the number \$b_1\$ appears \$k_1\$ times, \$b_2\$ \$k_2\$ times, etc. Then the uniformity of an array is the minimum integer \$c \geq 1\$ such that \$c \leq k_i\$ for any \$i\$.

As part of your research, you want to perform \$q\$ operations in sequence.

1. Operation \$t_i = 1, l_i, r_i\$ specifies a research request. It is necessary to deduce the uniformity of an array consisting of elements in positions from \$l_i\$ to \$r_i\$ inclusive.
2. Operation \$t_i = 2, p_i, x_i\$ specifies a request for data clarification. Starting from this point in time, the \$p_i\$th element of the array is assigned the value \$x_i\$.

Input format: The first line contains \$n\$ and \$q\$ (\$1 \leq n, q \leq 100\,000\$) - the size of the array and the number of queries, respectively. The second line contains exactly \$n\$ numbers - \$a_1, a_2, \ldots, a_n\$ (\$1 \leq a_i \leq 10^9\$). Each of the remaining \$q\$ lines specifies another query. The first type of query is specified by three numbers \$t_i = 1, l_i, r_i\$, where \$1 \leq l_i \leq r_i \leq n\$ are the boundaries of the corresponding segment. The second type of query is specified by three numbers \$t_i = 2, p_i, x_i\$, where \$1 \leq p_i \leq n\$ is the position at which the number needs to be replaced, and \$1 \leq x_i \leq 10^9\$ - its new meaning. Output format: For each query of the first type, print one number - the uniformity of the corresponding array segment.

Example

10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8

Answer:

2
3
2

Note: The first query consists of exactly one element - \$1\$. The minimum suitable \$c = 2\$. The second query segment consists of four \$2\$, one \$3\$ and two \$1\$. The minimum suitable \$c = 3\$. The segment of the fourth query consists of three \$1\$, three \$2\$ and one \$3\$. The minimum suitable \$c = 2\$.

My very first code:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

const int MAXN = 100000;
int n, q;
int a[MAXN];

int find_uniformity(const vector<int>& segment) {
    unordered_map<int, int> freq;
    for (int num : segment) {
        freq[num]++;
    }
    unordered_set<int> frequency_set;
    for (const auto& kv : freq) {
        frequency_set.insert(kv.second);
    }
    
    int c = 1;
    while (frequency_set.find(c) != frequency_set.end()) {
        c++;
    }
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            l--; r--;
            vector<int> segment(a + l, a + r + 1);
            int result = find_uniformity(segment);
            cout << result << endl;
        } else if (t == 2) {
            int p, x;
            cin >> p >> x;
            p--;
            a[p] = x;
        }
    }
    
    return 0;
}

But since it was running slow, I tried to optimize it using a segment tree, which is used to store the frequency of each element in a segment using an array of size MAXV + 1 (where MAXV is the maximum possible value in the array)

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

const int MAXN = 100000;
const int MAXA = 1000000000;
const int MAXV = 10;

struct SegmentTree {
    vector<vector<int>> tree;
    int size;
    
    SegmentTree(int n) {
        size = n;
        tree.resize(4 * n, vector<int>(MAXV + 1, 0));
    }
    
    void build(const vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node][arr[start]]++;
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            merge(tree[node], tree[2 * node + 1], tree[2 * node + 2]);
        }
    }
    
    void merge(vector<int>& parent, const vector<int>& left, const vector<int>& right) {
        for (int i = 1; i <= MAXV; i++) {
            parent[i] = left[i] + right[i];
        }
    }
    
    void update(int node, int start, int end, int idx, int old_val, int new_val) {
        if (start == end) {
            tree[node][old_val]--;
            tree[node][new_val]++;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(2 * node + 1, start, mid, idx, old_val, new_val);
            } else {
                update(2 * node + 2, mid + 1, end, idx, old_val, new_val);
            }
            merge(tree[node], tree[2 * node + 1], tree[2 * node + 2]);
        }
    }
    
    vector<int> query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return vector<int>(MAXV + 1, 0);
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        auto left = query(2 * node + 1, start, mid, l, r);
        auto right = query(2 * node + 2, mid + 1, end, l, r);
        vector<int> result(MAXV + 1, 0);
        merge(result, left, right);
        return result;
    }
};

int find_uniformity(const vector<int>& freq) {
    unordered_set<int> frequency_set;
    for (int f : freq) {
        if (f > 0) frequency_set.insert(f);
    }
    int c = 1;
    while (frequency_set.find(c) != frequency_set.end()) {
        c++;
    }
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    SegmentTree seg_tree(n);
    seg_tree.build(a, 0, 0, n - 1);

    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            l--; r--;
            auto freq = seg_tree.query(0, 0, n - 1, l, r);
            int result = find_uniformity(freq);
            cout << result << endl;
        } else if (t == 2) {
            int p, x;
            cin >> p >> x;
            p--;
            int old_val = a[p];
            a[p] = x;
            seg_tree.update(0, 0, n - 1, p, old_val, x);
        }
    }

    return 0;
}

It’s strange, but the code didn’t speed up significantly, as I would have liked, and I don’t know any other optimization algorithm in this case. Is it possible to somehow optimize this code or find a different algorithm?

It is worth noting that Fenwick Tree and Mo's Algorithm do not solve this problem, I tried...

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

const int MAXN = 100000;

struct FenwickTree {
    vector<int> tree;
    int size;
    
    FenwickTree(int n) {
        size = n;
        tree.resize(n + 1, 0);
    }
    
    void update(int index, int delta) {
        for (++index; index <= size; index += index & -index) {
            tree[index] += delta;
        }
    }
    
    int query(int index) {
        int sum = 0;
        for (++index; index > 0; index -= index & -index) {
            sum += tree[index];
        }
        return sum;
    }
    
    int range_query(int left, int right) {
        return query(right) - query(left - 1);
    }
};

int find_uniformity(const unordered_map<int, int>& freq_map) {
    unordered_set<int> frequency_set;
    for (const auto& kv : freq_map) {
        frequency_set.insert(kv.second);
    }
    int c = 1;
    while (frequency_set.find(c) != frequency_set.end()) {
        c++;
    }
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    FenwickTree fenwick(MAXN);
    unordered_map<int, int> freq;

    for (int i = 0; i < n; i++) {
        freq[a[i]]++;
        fenwick.update(a[i], 1);
    }

    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            l--; r--;

            unordered_map<int, int> segment_freq;
            for (int j = l; j <= r; j++) {
                segment_freq[a[j]]++;
            }
            
            int result = find_uniformity(segment_freq);
            cout << result << endl;
        } else if (t == 2) {
            int p, x;
            cin >> p >> x;
            p--;

            fenwick.update(a[p], -1);
            if (--freq[a[p]] == 0) {
                freq.erase(a[p]);
            }

            a[p] = x;

            fenwick.update(a[p], 1);
            freq[a[p]]++;
        }
    }

    return 0;
}

Answer 1

You wrote that the Mo's algorithm does not work, but the code you provided does not show it, the Fenwick Tree algorithm is presented in it, but I have not seen any attempts to solve the problem using the Mo's algorithm

Mo's algorithm is efficient by dividing the array into blocks and using query sorting to minimize the number of state changes between successive queries. In this case, Mo's algorithm has been modified to support queries to change array elements.

I want to analyze every moment of my code so that it’s clear what I’m working with, and then I’ll provide it in full

Constants and library

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
const int len = 1300;

here is the standard library <bits/stdc++.h>. \$maxn\$ is the maximum size of the array. \$len\$ is a constant in Mo's algorithm, usually equal to the square root of \$maxn\$.

Variables

int a[maxn];
vector<pair<int, int>> qw;
vector<pair<int, pair<int, int>>> upd;
vector<int> times;
vector<int> u;
vector<int> kol(maxn);
vector<int> now_a;

\$a\$ is an array of elements. \$qw\$ - stores queries in the range \$(l, r)\$. \$upd\$ stores update queries (\$p\$, old value, new value). \$times\$ tracks the time of each request regarding updates. \$u\$ counts the number of occurrences of each element. \$kol\$ counts how many numbers have a certain number of occurrences. \$now_a\$ keeps track of the current state of the array after each update.

Comparison function

bool comp(int a1, int a2) {
    pair<pair<int, int>, int> tmp1 = {{qw[a1].first / len, qw[a1].second / len}, times[a1]};
    pair<pair<int, int>, int> tmp2 = {{qw[a2].first / len, qw[a2].second / len}, times[a2]};
    return tmp1 < tmp2;
}

The comparison function \$comp\$ is used to sort queries. Requests are sorted first by block, then by right edge, and finally by request time.

Add and remove functions

void add(int el) {
    if (u[el] != 0)
        kol[u[el] - 1]--;
    u[el]++;
    kol[u[el] - 1]++;
}

void del(int el) {
    kol[u[el] - 1]--;
    u[el]--;
    if (u[el] != 0)
        kol[u[el] - 1]++;
}

\$add\$ adds an element to the current range, updating the occurrence count and corresponding counter. \$del\$ removes an element from the current range, updating the number of occurrences and the corresponding counter.

Main code

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5;
const int len = 1300;
int a[maxn];
vector<pair<int, int>> qw;
vector<pair<int, pair<int, int>>> upd;
vector<int> times;
vector<int> u;
vector<int> kol(maxn);
vector<int> now_a;

bool comp(int a1, int a2) {
    pair<pair<int, int>, int> tmp1 = {{qw[a1].first / len, qw[a1].second / len}, times[a1]};
    pair<pair<int, int>, int> tmp2 = {{qw[a2].first / len, qw[a2].second / len}, times[a2]};
    return tmp1 < tmp2;
}

void add(int el) {
    if (u[el] != 0)
        kol[u[el] - 1]--;
    u[el]++;
    kol[u[el] - 1]++;
}

void del(int el) {
    kol[u[el] - 1]--;
    u[el]--;
    if (u[el] != 0)
        kol[u[el] - 1]++;
}

int get() {
    for (int i = 0; i < kol.size(); ++i) {
        if (kol[i] == 0)return i + 1;
    }
    return -1;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n, q;
    cin >> n >> q;
    now_a.resize(n);
    unordered_map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (mp.count(a[i]) == 0)mp[a[i]] = mp.size();
        a[i] = mp[a[i]];
        now_a[i] = a[i];
    }
    vector<int> tt;
    int cnt = 0;
    for (int k = 0; k < q; ++k) {
        int c;
        cin >> c;
        if (c == 1) {
            int l, r;
            cin >> l >> r;
            l--;
            r--;
            qw.push_back({l, r});
            times.push_back(cnt - 1);
            tt.push_back(k - cnt);
        } else {
            cnt++;
            int p, x;
            cin >> p >> x;
            if (mp.count(x) == 0)mp[x] = mp.size();
            x = mp[x];
            p--;
            upd.push_back({p, {now_a[p], x}});
            now_a[p] = x;
        }
    }
    sort(tt.begin(), tt.end(), comp);
    u.resize(mp.size());
    int now = -1;
    int le = 0;
    int ri = -1;
    vector<int> ans(tt.size());
    for (int m = 0; m < tt.size(); ++m) {
        int id = tt[m];
        while (now < times[id]) {
            now++;
            int ps = upd[now].first;
            int from = upd[now].second.first;
            int to = upd[now].second.second;
            if (le <= ps && ps <= ri) {
                add(to);
                del(from);
            }
            a[ps] = to;
        }
        while (now > times[id]) {
            int ps = upd[now].first;
            int from = upd[now].second.first;
            int to = upd[now].second.second;
            if (le <= ps && ps <= ri) {
                add(from);
                del(to);
            }
            a[ps] = from;
            now--;
        }
        while (ri < qw[id].second) {
            ri++;
            add(a[ri]);
        }
        while (le > qw[id].first) {
            le--;
            add(a[le]);
        }
        while (ri > qw[id].second) {
            del(a[ri]);
            ri--;
        }
        while (le < qw[id].first) {
            del(a[le]);
            le++;
        }
        ans[id] = get();
    }
    for (int j = 0; j < tt.size(); ++j) {
        cout << ans[j] << "\n";
    }
}
```