Mos Algo With Update And Without Update In C++

An algorithm known as Mo’s Algorithm, an offline technique that incorporates square root decomposition of the array, is proficient in handling various operations like range query, sum calculation, frequency count, and more. By dividing the array into blocks of √N size, where N is the array size, it eliminates redundant calculations and enhances query processing efficiency. The queries are arranged based on their block index and then, within each block, by the endpoint of the query. This arrangement ensures minimal movements during the two-pointer approach (left and right pointers) while adding or removing elements within the current range.

In the traditional iteration of Mo's algorithm, the array remains constant without any modifications during the range queries. The queries undergo sorting before being methodically executed. Employing two pointers helps maintain the current range. Supporting structures, such as frequency arrays for tracking distinct values, enable swift additions and removals of elements in constant time. This method proves highly effective for unchanging arrays facing a substantial number of queries.

We require extra methods due to the array's dynamic nature, especially when modifications happen between queries like point updates. These changes can be managed offline by storing and processing them alongside queries, or online by utilizing auxiliary data structures like segment trees or Fenwick trees. The intricacy has escalated as updates to the array must be accounted for, ensuring effective responses to range queries on the updated array.

Afterward, although the static algorithm is ideal for unchanging arrays, the update-friendly algorithm sacrifices simplicity in favor of adaptability. These two variations are commonly employed to effectively address range query challenges in situations where straightforward approaches prove to be too sluggish.

Mo’s Algorithm with Updates

Mo's Algorithm is a proficient offline method for responding to range inquiries (such as sum, count, or frequency) on an array by employing square root decomposition. When addressing the static scenario, the array retains its traditional structure; however, when updates are introduced, Mo's Algorithm is expanded to effectively manage dynamic alterations.

In this edition, individual updates like altering a specific array element are merged with range inquiries. To handle updates effectively, the procedure utilizes two primary methods:

• ✅ Batch Updates: Updates and queries are pre-stored and executed collectively as a batch. Mo's block decomposition is applied to arrange queries and updates in order. The rollback feature enables reverting or reapplying updates as needed during query transitions.

Program:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
int blockSize;
int arr[MAXN], tempArr[MAXN];
int freq[MAXN];
int currentAnswer = 0;
vector<int> results;

struct Query {
    int L, R, id, time;
    Query(int L, int R, int id, int time) : L(L), R(R), id(id), time(time) {}
};

struct Update {
    int index, oldVal, newVal;
    Update(int index, int oldVal, int newVal) : index(index), oldVal(oldVal), newVal(newVal) {}
};

vector<Query> queries;
vector<Update> updates;

// Functions for Mo's Algorithm
void add(int idx) {
    freq[tempArr[idx]]++;
    if (freq[tempArr[idx]] == 1) currentAnswer++;
}

void remove(int idx) {
    if (freq[tempArr[idx]] == 1) currentAnswer--;
    freq[tempArr[idx]]--;
}

void applyUpdate(int time) {
    int idx = updates[time].index;
    if (updates[time].oldVal == updates[time].newVal) return;

    if (idx >= 0) { // Ensure the index is valid
        remove(idx);
        tempArr[idx] = updates[time].newVal;
        add(idx);
    }
}

void rollbackUpdate(int time) {
    int idx = updates[time].index;
    if (updates[time].oldVal == updates[time].newVal) return;

    remove(idx);
    tempArr[idx] = updates[time].oldVal;
    add(idx);
}

bool compare(const Query &a, const Query &b) {
    int blockA = a.L / blockSize, blockB = b.L / blockSize;
    if (blockA != blockB) return blockA < blockB;
    return ((blockA & 1) ? a.R > b.R : a.R < b.R);
}

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

    int n, q; // n = array size, q = total operations
    cin >> n >> q;
    blockSize = sqrt(n);

    // Input the initial array
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        tempArr[i] = arr[i];
    }

    int t = 0; // Tracks updates
    for (int i = 0; i < q; i++) {
        char type;
        cin >> type;
        if (type == 'Q') { // Query
            int L, R;
            cin >> L >> R;
            L--, R--; // Convert to 0-based indexing
            queries.emplace_back(L, R, results.size(), t);
            results.push_back(0);
        } else if (type == 'U') { // Update
            int index, newVal;
            cin >> index >> newVal;
            index--; // Convert to 0-based indexing
            updates.emplace_back(index, tempArr[index], newVal);
            tempArr[index] = newVal; // Apply temporarily
            t++;
        }
    }

    // Sort queries using Mo's ordering
    sort(queries.begin(), queries.end(), compare);

    int L = 0, R = -1, time = 0;
    for (auto &q : queries) {
        while (time < q.time) { applyUpdate(time); time++; }
        while (time > q.time) { time--; rollbackUpdate(time); }
        while (L < q.L) remove(L++);
        while (L > q.L) add(--L);
        while (R < q.R) add(++R);
        while (R > q.R) remove(R--);

        results[q.id] = currentAnswer;
    }

    for (auto res : results) {
        cout << res << '\n';
    }

    return 0;
}

Output:

5 6 
1 2 1 3 2 
Q 1 5 
U 3 4 
Q 1 5 
U 1 2 
Q 1 3 
Q 2 5
3
4
2
3

Explanation:

Initialization:

The algorithm processes both the input array and queries. The elements in the original array arr and the temporary array for processing (tempArr) are populated accordingly. The currentAnswer stores the outcome of the range query, while the freq array records the occurrence of elements within the specified query range.

Queries and Revisions:

• ✅ Interrogation (Q L R): This action provides a count of the unique elements within the array range from L to R.
• ✅ Modification (U i x): This process involves substituting the value x into the list at the specified index i.

These actions are handled in two separate arrays:

• ✅ queries: This array holds all the queries.
• ✅ updates: All updates are stored here, encompassing the update index, the previous value, and the new value.

Sorting Queries:

Queries are arranged by applying a personalized comparison function that relies on the Mo's Algorithm technique:

We divide the array into segments containing approximately √N elements each. Initially, arrange queries based on the starting block of the left endpoint (L) and then by the right endpoint (R). When handling two queries within the same block, prioritize sorting them by their right endpoint to decrease recalculations. This sorting methodology helps to cut down on repetitive computations and limits the adjustments needed for the query range pointers.

Handling Updates

Updates are implemented or undone through the following functions:

• ✅ applyUpdate(time): This function applies updates at a particular "time" on the update timeline.
• ✅ rollbackUpdate(time): It restores the array element to its initial value, executing a rollback by reversing the specific array element.

The tempArr and freq arrays are updated to incorporate these adjustments, and the tempArr array is altered by whichever function is implemented.

Query Execution:

Processing the pair of L and R pointers that define the current range is underway. Each query involves adjusting the pointers to cover the range [L, R] and includes adding or removing elements as needed. The outcomes of these queries are recorded in the results array.

Complexity Analysis:

Time Complexity

Three factors primarily determine the time complexity of Mo's Algorithm with offline updates:

• ✅ Sorting Queries: They sort the queries based on their left endpoints ('L') and their right endpoints ('R'). There is sorting (O(Q/ log Q)), where (Q) is the number of queries.
• ✅ Processing Queries: For each query, the algorithm changes the left and righcpp tutorialers (L, R). Each adjustment takes (O(sqrt {N})) time, where (N) is the size of the array. It implies that we process (O(Q sqrt{N})).
• ✅ Handling Updates: On any update, updates are applied and rolled back as necessary, which also (O(sqrt{N})) for each update. This (O(Usqrt{N})) with (U) updates.

Consequently, the overall time complexity amounts to (O((Q + U) sqrt{N})).

Space Complexity

The storage requirements determine the space complexity:

• ✅ The 'arr' and 'tempArr' will need (O(N)) space.
• ✅ In order to store 1st appearance of elements in the 'freq' array, we require (O(N)) space.
• ✅ The number of bits to store queries and updates takes (O(Q + U)).

Hence, the overall spatial complexity amounts to (O(N + Q + U)).

1. Real-time Updates: To handle updates and range queries promptly, we employ data structures like Segment Trees or Fenwick Trees (also known as binary-indexed trees).

Program:

#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
    vector<int> tree, lazy;
    SegmentTree(int n) {
        tree.resize(4 * n, 0);
        lazy.resize(4 * n, -1);
    }
    void propagate(int node, int start, int end) {
        if (lazy[node] != -1) {
            tree[node] = (end - start + 1) * lazy[node];
            if (start != end) {
                lazy[2 * node + 1] = lazy[node];
                lazy[2 * node + 2] = lazy[node];
            }
            lazy[node] = -1;
        }
    }
    void updateRange(int node, int start, int end, int l, int r, int value) {
        propagate(node, start, end);
        if (start > end || start > r || end < l) return;
        if (start >= l && end <= r) {
            tree[node] = (end - start + 1) * value;
            if (start != end) {
                lazy[2 * node + 1] = value;
                lazy[2 * node + 2] = value;
            }
            return;
        }
        int mid = (start + end) / 2;
        updateRange(2 * node + 1, start, mid, l, r, value);
        updateRange(2 * node + 2, mid + 1, end, l, r, value);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
    int queryRange(int node, int start, int end, int l, int r) {
        propagate(node, start, end);
        if (start > end || start > r || end < l) return 0;
        if (start >= l && end <= r) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        int leftQuery = queryRange(2 * node + 1, start, mid, l, r);
        int rightQuery = queryRange(2 * node + 2, mid + 1, end, l, r);
        return leftQuery + rightQuery;
    }
};

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

    int n, q;
    cin >> n >> q;
    vector<int> arr(n);
    SegmentTree segTree(n);

    // Input the initial array
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        segTree.updateRange(0, 0, n - 1, i, i, arr[i]);
    }

    // Process queries
    while (q--) {
        char type;
        cin >> type;
        if (type == 'Q') {
            int L, R;
            cin >> L >> R;
            L--, R--; // Convert to 0-indexed
            cout << segTree.queryRange(0, 0, n - 1, L, R) << '\n';
        } else if (type == 'U') {
            int index, newVal;
            cin >> index >> newVal;
            index--; // Convert to 0-indexed
            segTree.updateRange(0, 0, n - 1, index, index, newVal);
        }
    }

    return 0;
}

Output:

3 4
1 3 1
Q 1 5
U 2 4
Q 1 2
U 3 4
9
5

Explanation:

• ✅ Input: The Input begins with two integers: The query has n (size of the array) and q (number of operations). After that, q operations take place, where each is a query (Q L R) to count distinct elements of the range [L, R] or an update (U i x), making the value at index i x.
• ✅ Segment Tree: The Segment Tree efficiently makes various point updates and range queries. Queries update a portion of the array and return the number of distinct elements in a given range.
• ✅ Mo's Algorithm: Mo's Algorithm processes the queries and sorts them to minimize the movement of the range pointers and the total time complexity. We do this by sorting the queries by their left index and right index and then adjusting each query's current range to match it.
• ✅ Updates: The Segment Tree is updated whenever point updates are made and whichever part of the array is modified. Updates can occur between range queries, and the tree guarantees that these range queries still provide the correct results.

The software accepts a query as input and returns the count of unique elements within the specified range for each query. It handles range queries, performs updates, and displays the outcomes.

Complexity Analysis

Time Complexity:

Here, arranging the queries incurs a time complexity of (O(Q log Q)), where (Q) represents the quantity of queries. Each query involves adjusting the range, requiring (O(log N)) time due to the Segment Tree. The overall expense of executing all queries amounts to (O(Q log N)). The process of updating includes modifying the Segment Tree, along with (O(log N)) for each update. Consequently, our updates demand a total time of (O(U log N)), with (U) denoting the count of updates. This culminates in a total time complexity of (O((Q+U)log N)).

Space Complexity:

It is the Segment Tree and additional data structures that impact the space complexity. The Segment Tree alone requires (O(N)) space, similar to the storage needed for queries, outcomes, and auxiliary data arrays. The time and space complexity of this issue is (O(N + Q + U)).

Mo’s Algorithm without Updates

Mo's Algorithm is an efficient method for handling multiple range queries on an unchanging array. It finds particular utility in tasks like determining the total, minimum, or maximum within a specified range, or counting the unique elements within a range. The fundamental concept behind Mo's Algorithm involves rearranging queries to reduce the amount of movement in adjusting the boundaries of the range (represented by pointers L and R).

To accomplish this, square root decomposition is implemented. The array is divided into segments of approximately size N, and the queries are arranged based on their starting and ending points. Mo's Algorithm aids in handling queries sequentially to minimize repetitive computations and enhance computational efficiency.

Program:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000; // Maximum size of the array
int arr[MAXN], freq[MAXN];
int blockSize;
int currentAnswer = 0;
// Query structure
struct Query {
    int L, R, id;
    Query(int L, int R, int id) : L(L), R(R), id(id) {}
};

// Compare function to sort queries in Mo's order
bool compare(const Query &a, const Query &b) {
    int blockA = a.L / blockSize, blockB = b.L / blockSize;
    if (blockA != blockB) return blockA < blockB;
    return ((blockA & 1) ? a.R > b.R : a.R < b.R);
}
// Add an element to the current range
void add(int index) {
    int element = arr[index];
    freq[element]++;
    if (freq[element] == 1) { // First occurrence of the element
        currentAnswer++;
    }
}
// Remove an element from the current range
void remove(int index) {
    int element = arr[index];
    freq[element]--;
    if (freq[element] == 0) { // Element no longer present
        currentAnswer--;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    // Input the array
    vector<int> compressedArr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        compressedArr[i] = arr[i];
    }
    // Coordinate compression
    sort(compressedArr.begin(), compressedArr.end());
    compressedArr.erase(unique(compressedArr.begin(), compressedArr.end()), compressedArr.end());
    for (int i = 0; i < n; i++) {
        arr[i] = lower_bound(compressedArr.begin(), compressedArr.end(), arr[i]) - compressedArr.begin();
    }

    // Adjust freq array size
    int maxVal = compressedArr.size();
    memset(freq, 0, maxVal * sizeof(int));
    // Block size for Mo's Algorithm
    blockSize = sqrt(n);
    // Store the queries
    vector<Query> queries;
    vector<int> results(q);
    for (int i = 0; i < q; i++) {
        int L, R;
        cin >> L >> R;
        L--, R--; // 0-indexed
        queries.emplace_back(L, R, i);
    }
    // Sort queries based on Mo's algorithm sorting criteria
    sort(queries.begin(), queries.end(), compare);
    // Process each query
    int L = 0, R = -1; // Initial range is empty
    for (auto &query : queries) {
        // Adjust the range to [query.L, query.R]
        while (R < query.R) {
            R++;
            add(R);
        }
        while (R > query.R) {
            remove(R);
            R--;
        }
        while (L < query.L) {
            remove(L);
            L++;
        }
        while (L > query.L) {
            L--;
            add(L);
        }
        // Store the result for the current query
        results[query.id] = currentAnswer;
    }

    // Output all results
    for (int res : results) {
        cout << res << "\n";
    }
    return 0;
}

Output:

5 3
1 2 1 3 2
1 3
2 5
1 5
2
3
3

Explanation:

Input:

The initial segment of the code is responsible for receiving input values. At the outset, there are two values on the first line: n, denoting the array's size, and q, representing the number of queries. Subsequently, the array arr with n elements is formed based on the input values. Following this, the code proceeds to handle the queries. Each query comprises a pair of integers, L and R, specifying a particular range within which the count of unique elements needs to be determined. To manage these queries efficiently, a vector containing Query structures is employed for storage.

Sorting Queries:

The goal of Mo's Algorithm is to rearrange the queries in a way that minimizes the movement of the pointers L and R.

Queries are arranged by L divided by blockSize, and within each block by the block number of the left endpoint (L/blockSize) and by the block number of the right endpoint R. The sorting of queries was done in a descending order of R with an extra optimization based on whether the block number was odd or even.

• ✅ insert: This function is utilized when expanding R (extending the range to the right). Its purpose is to increment the count of unique elements and update the element's frequency if it's the first occurrence.
• ✅ delete: When narrowing the range from both ends - either by decreasing R (to the right) or increasing L (to the left) - this function is invoked. It reduces the frequency of the element if it's greater than 1, and if the frequency drops to zero, it reduces the count of distinct elements.

Processing Queries:

• ✅ The range of the query changes the left and righcpp tutorialers (L and R) for every query.
• ✅ In currentAnswer, we store the number of distinct elements in the current range, which is updated dynamically as elements are added or removed.
• ✅ All queries are processed, and the answers are Outputd in the order in which the original query appeared.

Complexity Analysis:

Time Complexity:

When it comes to

• ✅ Sorting Queries, the process involves interfacing with the data structure directly, resulting in a time complexity of O(Q log Q), where Q represents the total number of queries. This efficiency is achieved by sorting the queries based on their left and right bounds. The implementation of Mo's algorithm focuses on optimizing this sorting to minimize the movement of the pointers, left and right.

On the other hand, for

• ✅ Processing Queries, the adjustments are made to the range by iteratively moving the left and right pointers for each query. This adjustment operation for each query requires O(sqrt{N}) time, where N denotes the size of the array. Considering there are Q queries in total, the overall time complexity to process all queries sums up to O(Q (sqrt{N})).

It all adds up to a combined complexity of (O((Q + N) sqrt{N})) where (N) represents the array's size and (Q) indicates the number of queries.

Space Complexity:

The allocation of memory for the array, frequency array, and queries significantly impacts the space complexity:

The array requires (O(N)) space complexity. An additional (O(N)) space is necessary for the frequency array used to tally elements. Allocating (O(Q)) space is essential for holding the queries. Consequently, the space complexity of this algorithm totals (O(N + Q)).