Venice Technique is a strategy where we create a new data structure called Venice Set that mainly helps to answer range queries which involves updating all elements by a common value in constant time. In this article, we will discuss about Venice Technique, the idea behind Venice Technique, its structure, implementation, etc.

What is Venice Set?

Venice Set is a user defined data structure that contains different types of data(usually numbers) and these three different types of operations-

• Add any element to the set
• Remove any element of the set
• Update all elements by a common value

Syntax :

class VeniceSet:

def add(self, value): pass # Adds an element to the set

def remove(self, value): pass # Removes an element from the set

def update_all(self, delta): pass # Updates all elements by a common value

This syntax outlines the core methods of the Venice Set for adding, removing and updating elements.

Apart from that, we can also add a method for finding the Venice set’s size. We can add other methods as well in the venice sets according to our need.

We mainly take unordered sets, sets or multisets to implement venice sets. We already know how to add or remove any element in constant time, but the main reason of bringing venice set into the picture is to update all element into a constant time.

Idea behind Venice Technique:

In a city, the government decided to build some towers such that it could tell workers anytime to add any tower, remove any tower, or to reduce the height of all towers by a common value. Now adding and removing any tower can be done in constant time but to reduce the height of all towers by a common value, workers have to go to every tower to reduce the height.

So, to reduce the height of all towers in constant time, what workers can do is to put water in the whole city so that the bottom part of the tower can be submerged in water by the same amount with which we needed to reduce the height. For example, if the Government instructs to reduce every tower’s height by 1 unit, then workers can put water in the city so that the bottom most 1 unit of towers get submerged in water. We will do the same thing in Venice set to update all elements by a common value in constant time.

Now since Venice is a city in Italy in which there is water between houses and in this set like data structure we are updating all elements by water or some value. So to easily identify this data structure we called that Venice set.

Structure of Venice Set:

Below is the structure of Venice Set:

struct VeniceSet {
    void add(int);
    void remove(int);
    void updateAll(int);
    int size();
};

struct VeniceSet {
    void add(int);
    void remove(int);
    void updateAll(int);
    int size();
};

Step-by-step algorithm:

Now algorithm for implementation of these methods depends on use cases. So here we will implement these methods for the problem that we saw earlier where the Government wants to add, remove, or reduce the height of all the towers in constant time. Here, we should take care of the following points-

• Take multiset instead of set because there can be multiple towers of the same length.
• Take a variable of any name, let us call that water_level.
  • Initially, that variable will contain zero because there is no instruction to reduce the length of the tower.
  • In the future, if we have to remove some part of every tower we will update that variable.
• On adding any tower, don’t directly add any tower length to the multiset, instead add (tower + water_level).
• On removing any tower don’t directly remove any effective tower length from the multiset, instead remove (tower + water_level).
• We are removing “tower + water_level” because while adding we added the length of the tower from the ground.
• In updateAll we will simply update the water level by adding the size of the part of tower in it that we want to remove.
• In size simply return the size of the multiset because that will be the size of Venice set.

Implementation of Venice Technique

Below is the implementation of Venice Technique:

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

struct VeniceSet {
    multiset<int> St;
    int water_level = 0;

    void add(int x) { St.insert(x + water_level); }

    void remove(int x)
    {
        auto it = St.find(x + water_level);
        if (it != St.end()) {
            St.erase(it);
        }
        else {
            cout << "Element " << x
                 << " not found for removal." << endl;
        }
    }

    void updateAll(int x) { water_level += x; }

    int size() { return St.size(); }
};

int main()
{
    VeniceSet vs;

    // Add elements to the VeniceSet
    vs.add(10);
    vs.add(20);
    vs.add(30);

    // Print size of the set
    cout << "Size of the set: " << vs.size() << endl;

    // Decrease all by 5
    vs.updateAll(5);

    // Remove an element
    // This removes 5 (present height) + 5 (water level) = 10
    vs.remove(5);

    // Attempt to remove an element that does not exist
    vs.remove(40);

    // Print size of the set
    cout << "Size of the set: " << vs.size() << endl;

    return 0;
}

Size of the set: 3
Element 40 not found for removal.
Size of the set: 2

Complexity Analysis:

• For add operation: O(log(n)), because insertion in multiset takes log(n) time
• For remove operation: O(log(n)), because finding any element takes log(n) time and erasing any element also takes log(n) time, so overall log(n)+log(n)=2log(n)=log(n)
• For updating all element: O(1)