Выполнять запросы на добавление, обновление, удаление и ранжирование суммы в заданном массиве

Опубликовано: 7 Января, 2022

Дан массив arr [] размера N, и задача состоит в том, чтобы ответить на Q запросов следующих типов:

  • 1 X 0: добавить X в конец массива.
  • 2 XY: установите arr [X] = Y.
  • 3 X 0: удалить arr [X] .
  • 4 XY: Найдите сумму в диапазоне [X, Y] .

Обратите внимание, что после удаления arr [X] в типе запроса 3 все элементы после индекса X будут сдвинуты влево на одну позицию.
Примеры:

Input: arr[] = {1, 2, 5, 3, 4}, Q[][] = { 
{4, 2, 4}, 
{3, 3, 0}, 
{1, 6, 0}, 
{4, 3, 5}} 
Output: 
10 
13
First Query -> sum(arr[1], arr[2], arr[3]) 
Second Query -> arr[] = { 1, 2, 3, 4 } 
Third Query -> arr[] = { 1, 2, 3, 4, 6 } 
Fourth Query -> sum(arr[2], arr[3], arr[4])
Input: arr[] = {1, 2, 3, 4, 5}, Q[][] = { 
{4, 1, 5}, 
{3, 3, 0}, 
{1, 6, 0}, 
{4, 3, 5}, 
{2, 4, 10}. 
{4, 1, 5}} 
Output: 
15 
15 
23 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: наивный способ решить эту проблему - выполнить запросы непосредственно к заданному массиву, который будет иметь временную сложность O (Q * N) .
Эффективный подход:

  • Поскольку есть некоторые структуры данных, такие как дерево сегментов или BIT (дерево Фенвика), которые обеспечивают обновление точки и сумму диапазона в O (logN) для каждого запроса.
  • Там пост использует дерево Фенвика, чтобы сделать то же самое, поэтому настоятельно рекомендуется пройти обновление точки в Дереве Фенвика.
  • Но основная проблема заключается в выполнении операции удаления ( запросы типа 3 ), после выполнения требуется сдвиг, который снова приведет к O (Q * N) в худшем случае.
  • Можно использовать уловку, заключающуюся в том, что после удаления элемента просто обновите значение в A [X] = 0 и сопоставьте индекс после X с X + количество элементов, удаленных до X.
  • Чтобы найти количество элементов, удаленных до X , будет использоваться другое дерево Фенвика (как idx в реализации) и продолжать добавлять 1 в том индексе, где выполняется операция удаления.
  • Означает, что во время выборки или получения определенного индекса можно сделать запрос к дереву idx и обновить индекс X до X + sum (X, idx) .

Below is the implementation of the above approach: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Size of the array (MAX)
const int N = 2e5 + 10;
 
// To store the sum of
// the array elements
vector<int> bit(N, 0);
 
// To keep track of how many type 3
// queries have been performed before
// a particular index
vector<int> idx(N, 0);
 
// Function to perform the point
// update in Fenwick tree
void update(int idx, int val,
            vector<int>& bitt)
{
    while (idx < N) {
        bitt[idx] += val;
        idx += idx & (-idx);
    }
}
 
// Function to return the sum
// of the elements A[1...idx]
// from BIT
int sum(int idx,
        vector<int>& bitt)
{
 
    int res = 0;
    while (idx > 0) {
        res += bitt[idx];
        idx -= idx & (-idx);
    }
 
    return res;
}
 
// Function to perform the queries and
// return the answer vector
vector<int> peformQueries(vector<int>& A,
                          vector<vector<int> >& B)
{
 
    // For 1 bases indexing
    // insert 0 in the vector
    A.insert(A.begin(), 0);
 
    // Updated size of the vector
    int n = (int)A.size();
 
    // Updating the bit tree
    for (int i = 1; i < n; ++i) {
        update(i, A[i], bit);
    }
 
    // Vector to store the answers
    // of range sum
    vector<int> ans;
 
    // Iterating in the query
    // vector
    for (auto i : B) {
 
        int type = i[0];
        int x = i[1], v = i[2];
 
        // If the query is of
        // type 1
        if (type == 1) {
 
            // Updating the tree
            // with x in the last
            update(n, x, bit);
 
            // Pushing back the value
            // in the original vector
            A.push_back(x);
 
            // Incrementing the size
            // of the vector by 1
            n++;
        }
 
        // If the query is of type 2
        else if (type == 2) {
 
            // Getting the updated index
            // in case of any query of
            // type 3 occured before it
            int id = x + sum(x, idx);
 
            // Making the effect to that
            // value to 0 by subtracting
            // same value from the tree
            update(id, -A[id], bit);
 
            // Updating the A[id] to v
            A[id] = v;
 
            // Now update the
            // bit by v at x
            update(id, v, bit);
        }
 
        // If the query is of type 3
        else if (type == 3) {
 
            // Get the current index
            int id = x + sum(x, idx);
 
            // Remove the effect of that
            // index from the bit tree
            update(id, -A[id], bit);
 
            // Update the idx tree
            // because one element has
            // been deleted
            update(x, 1, idx);
 
            // Update the idx val to 0
            A[id] = 0;
        }
 
        // If the query is of type 4
        else {
 
            // Get the updated range
            int xx = x + sum(x, idx);
            int vv = v + sum(v, idx);
 
            // Push_back the value
            ans.push_back(sum(vv, bit)
                          - sum(xx - 1, bit));
        }
    }
 
    return ans;
}
 
// Driver code
int main()
{
    vector<int> A = { 1, 2, 5, 3, 4 };
 
    // Queries
    vector<vector<int> > B = {
        { 4, 2, 4 },
        { 3, 3, 0 },
        { 1, 6, 0 },
        { 4, 3, 5 },
    };
 
    // Get the answer array
    vector<int> ans = peformQueries(A, B);
 
    // printing the answer
    for (int i : ans)
        cout << i << " ";
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG {
 
    // Size of the array (MAX)
    static int N = (int) 2e5 + 10;
 
    // To store the sum of
    // the array elements
    static int[] bit = new int[N];
 
    // To keep track of how many type 3
    // queries have been performed before
    // a particular index
    static int[] idx = new int[N];
 
    // Function to perform the point
    // update in Fenwick tree
    static void update(int idx, int val, int[] bitt) {
        while (idx < N) {
            bitt[idx] += val;
            idx += idx & (-idx);
        }
    }
 
    // Function to return the sum
    // of the elements A[1...idx]
    // from BIT
    static int sum(int idx, int[] bitt) {
 
        int res = 0;
        while (idx > 0) {
            res += bitt[idx];
            idx -= idx & (-idx);
        }
 
        return res;
    }
 
    // Function to perform the queries and
    // return the answer vector
    static Vector<Integer> peformQueries(Vector<Integer> A, int[][] B) {
 
        // For 1 bases indexing
        // insert 0 in the vector
        A.insertElementAt(0, 0);
 
        // Updated size of the vector
        int n = (int) A.size();
 
        // Updating the bit tree
        for (int i = 1; i < n; ++i) {
            update(i, A.elementAt(i), bit);
        }
 
        // Vector to store the answers
        // of range sum
        Vector<Integer> ans = new Vector<>();
 
        // Iterating in the query
        // vector
        for (int[] i : B) {
 
            int type = i[0];
            int x = i[1], v = i[2];
 
            // If the query is of
            // type 1
            if (type == 1) {
 
                // Updating the tree
                // with x in the last
                update(n, x, bit);
 
                // Pushing back the value
                // in the original vector
                A.add(x);
 
                // Incrementing the size
                // of the vector by 1
                n++;
            }
 
            // If the query is of type 2
            else if (type == 2) {
 
                // Getting the updated index
                // in case of any query of
                // type 3 occured before it
                int id = x + sum(x, idx);
 
                // Making the effect to that
                // value to 0 by subtracting
                // same value from the tree
                update(id, -A.elementAt(id), bit);
 
                // Updating the A[id] to v
                A.set(id, v);
 
                // Now update the
                // bit by v at x
                update(id, v, bit);
            }
 
            // If the query is of type 3
            else if (type == 3) {
 
                // Get the current index
                int id = x + sum(x, idx);
 
                // Remove the effect of that
                // index from the bit tree
                update(id, -A.elementAt(id), bit);
 
                // Update the idx tree
                // because one element has
                // been deleted
                update(x, 1, idx);
 
                // Update the idx val to 0
                A.set(id, 0);
            }
 
            // If the query is of type 4
            else {
 
                // Get the updated range
                int xx = x + sum(x, idx);
                int vv = v + sum(v, idx);
 
                // Push_back the value
                ans.add(sum(vv, bit) - sum(xx - 1, bit));
            }
        }
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args) {
        Integer[] a = { 1, 2, 5, 3, 4 };
        Vector<Integer> A = new Vector<Integer>(Arrays.asList(a));
 
        // Queries
        int[][] B = { { 4, 2, 4 }, { 3, 3, 0 }, { 1, 6, 0 }, { 4, 3, 5 } };
 
        // Get the answer array
        Vector<Integer> ans = peformQueries(A, B);
 
        // printing the answer
        for (int i : ans)
            System.out.println(i);
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python implementation of the approach
 
# Size of the array (MAX)
N = int(2e5) + 10
 
# To store the sum of
# the array elements
bit = [0] * N
 
# To keep track of how many type 3
# queries have been performed before
# a particular index
idx = [0] * N
 
# Function to perform the point
# update in Fenwick tree
def update(index: int, val: int, bitt: list):
    while index < N:
        bitt[index] += val
        index += index & -index
 
# Function to return the sum
# of the elements A[1...idx]
# from BIT
def summation(index: int, bitt: list) -> int:
    res = 0
    while index > 0:
        res += bitt[index]
        index -= index & -index
    return res
 
# Function to perform the queries and
# return the answer vector
def performQueries(A: list, B: list) -> list:
    global bit, idx
 
    # For 1 bases indexing
    # insert 0 in the vector
    A.insert(0, 0)
 
    # Updated size of the vector
    n = len(A)
 
    # Updating the bit tree
    for i in range(1
Олимпиады по программированию Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Настройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023