### cjtoribio's blog

By cjtoribio, history, 8 months ago, ,

## Motivation & Problem

Recently saw this problem. For some this problem might seem like a segment tree problem and it is indeed one. However this problem and others where segment tree does not apply can be solved using another approach. I will rephrase the problem in a simpler way. We want a data structure capable of doing three main update-operations and some sort of query. The three modify operations are:

remove: Remove an element from the set.

updateAll: This one normally changes in this case subtract X from ALL the elements. For this technique it is completely required that the update is done to ALL the values in the set equally.

And also for this problem in particular we may need one query:

getMin: Give me the smallest number in the set.

Observing this operations we want to handle, SegmentTree seems legit except for the remove, but we can wave it around by assigning INF to the position we want to remove. However if we don't have the updateAll then we can just use a MULTISET. And in fact if the remove is only to the minimum element then we can use a HEAP. However the four operations without any "workaround" can only be managed by a DynamicSegmentTree which in fact exists but is like using a bazooka to kill a simple mosquito.

## Interface of the Data Structure

struct VeniceSet {
void remove(int);
void updateAll(int);
int getMin(); // custom for this problem
int size();
};


## Usage of this methods

So imaging we have this four operations, how can we tackle this problem with it. Well i will illustrate it with a simple code in C++ which i hope is self explanatory.

VeniceSet mySet;
for (int i = 0; i < N; ++i) {
mySet.updateAll(T[i]); // decrease all by T[i]
int total = T[i] * mySet.size(); // we subtracted T[i] from all elements

// in fact some elements were already less than T[i]. So we probbaly are counting
// more than what we really subtracted. So we look for all those elements
while (mySet.getMin() < 0) {
// get the negative number which we really did not subtracted T[i]
int toLow = mySet.getMin();

// remove from total the amount we over counted
total -= abs(toLow);

// remove it from the set since I will never be able to substract from it again
mySet.remove(toLow);
}
cout << total << endl;
}
cout << endl;


## Implementation of the Technique

As the title says I don't call it a data structure itself but this is a technique almost always backed up by a data structure. And now I am going to explain why I call it Venice technique. Imagine you have an empty land and the government can make queries of the following type: * Make a building with A floors. * Remove a building with B floors. * Remove C floors from all the buildings. (A lot of buildings can be vanished) * Which is the smallest standing building. (Obviously buildings which are already banished don't count)

The operations 1,2 and 4 seems very easy with a set, but the 3 is very cost effective probably O(N) so you might need a lot of workers. But what if instead of removing C floors we just fill the streets with enough water (as in venice) to cover up the first C floors of all the buildings :O. Well that seems like cheating but at least those floor are now vanished :). So in order to do that we apart from the SET we can maintain a global variable which is the water level. so in fact if we have an element and want to know the number of floors it has we can just do height - water_level and in fact after water level is for example 80. If we want to make a building of 3 floors we must make it of 83 floors so that it can tough the land. So the implementation of this technique might look like this.

struct VeniceSet {
multiset<int> S;
int water_level = 0;
S.insert(v + water_level);
}
void remove(int v) {
S.erase(S.find(v + water_level));
}
void updateAll(int v) {
water_level += v;
}
int getMin() {
return *S.begin() - water_level;
}
int size() {
return S.size();
}
};


## Variations

#### Trick With Trie

Probably you have seen a problem of having a set of numbers and handle queries such as what is the greatest XOR than can be achieved by using one number of the set and the given number. This can be handled with a BinaryTrie. However if we add the operation XOR all the numbers in the set this would be very heavy. But if we maintain a global water_level that would XOR any number in and any number out, then it would virtually be XORING all the numbers in the set. Don't have an example problem yet, but I know I have used it, so any is welcome.

So as my experience is, this technique is a lightweight modification that can be applied to all DataStructures that support (add, remove and query) and only need the operation (updateAll).

## Other Approaches For This Problem

Binary Search: This is very fast and simple, however is an offline solution. (Not apply for other operations such as sort)

Event Processing: Easy to code and fast but still offline and does not apply for other operations such as XOR.

Dynamic Segment Tree: A little slow in practice, same complexity in theory, and requires heavy code. This is online but requires heavy code. (Dynamic means can insert and delete nodes from the segment tree). Does not apply to other variations of the problem such as XOR.

Implicit Segment Tree: Relativly easy to code, but theoretical complexity of Nlog(MAXVAL) and still requires this technique to work. (Does not apply to other variations such as XOR)

## Example Problems

•
• +80
•

 » 8 months ago, # |   +73 Great article, but I usually use Pasha Technique.
•  » » 8 months ago, # ^ |   +3 Mmmh really good to know, could you describe it a little bit or point at some code using it? Is just to know all other approaches and point it out in the article. Thanks.
•  » » 8 months ago, # ^ |   +23 What's Pasha Technique?
•  » » » 8 months ago, # ^ |   0 its russian hero
•  » » 8 months ago, # ^ |   +9 Wish I could upvote twice
•  » » » 8 months ago, # ^ |   -24 this kid looks like trash
 » 8 months ago, # | ← Rev. 2 →   -40 Great article! Surely helps gray coders like me become better at problem solving. :pEDIT: I was being purely honest with the comment. No need to downvote.
 » 8 months ago, # | ← Rev. 3 →   +8 Shouldn't the correct code be like this? void remove(int v) { S.erase(S.find(v + waterlevel)); } int getMin() { return *S.begin() - waterlevel; } Otherwise you sometimes need to handle the water_level manually (min, remove), and sometimes not (add), which would be really strange.
•  » » 8 months ago, # ^ |   0 You are right, i am fixing it. thanks
 » 8 months ago, # |   0 Auto comment: topic has been updated by cjtoribio (previous revision, new revision, compare).
 » 8 months ago, # |   0 Nice analogy. It would be useful some links to problems using this technique or data structures using it too ... anybody ???
•  » » 8 months ago, # ^ |   +1 You may try the following: BDOI16E
•  » » » 8 months ago, # ^ |   0 Hmm the problem seems interesting. I'm still trying to find a solution applying the technique. Can you give some hint ?? Thanks for the link!!!
•  » » » » 8 months ago, # ^ |   +1 HintDSU on Tree (Small to large set merge trick)Not sure if I overkilled it though
•  » » » » » 8 months ago, # ^ |   0 That's what i was using to solve it, and not sure if i over-killed too. I was thinking in a simpler solution (like using the technique discussed here only or something). Thanks !!!
 » 8 months ago, # |   0 Cool. Trick
 » 8 months ago, # | ← Rev. 2 →   -29 Coulda simply used bitset LOL xD lulzUPD: Sorry, at first I thought this was a troll post. I didn't intend to offend anybody.
 » 8 months ago, # |   0 I also did a similar thing during the contest. I used a dynamic segment tree but instead of performing lazy propagation for update all I used similar technique of maintaining a level. Link to my submission : http://codeforces.com/contest/948/submission/36168355 In the code anss contains the current level.
 » 8 months ago, # |   0 But you can't remove buildings in civ, not even when playing Venice.
 » 8 months ago, # |   0 In the trie variation, what is the benefit of keeping the XOR of all numbers in the set???
•  » » 8 months ago, # ^ |   0 You dont have a XOR of all the numbers in the set you just have a lazy XOR that you want to apply to all the elements in the set. Instead of applying to the numbers you apply to each query you are asked, as we does with the ADD.
 » 8 months ago, # |   0 Nice tutorial! GOOD JOB!!!
 » 8 months ago, # |   +5 I've used this before but never knew it had a name.http://codeforces.com/problemset/problem/893/DVenice technique + prefix sums
•  » » 8 months ago, # ^ |   0 I made the name up. Definitely a lot of tricks have no name and that is why it is hard to find articles about it :(. That is why I wanted to come with one in case people want to adopt that name or at least put another one.
•  » » » 8 months ago, # ^ |   +69 What if some simple tricks, like "let's store one variable with global shift", don't need any names and articles, because it's very intuitive for specific task, and one sentence can fully describe this trick?
•  » » » » 8 months ago, # ^ |   +8 It adds an element of humor. E.g. the Trump technique would be related to tweeting
 » 8 months ago, # |   0 D. Vitya and Strange LessonAn example problem for Trie variation.
 » 8 months ago, # |   0 What is Event Processing? When I google it, I can't find any information related to competitive programming.
 » 8 months ago, # |   -13 গুদ জব।
 » 8 months ago, # |   0 Can you please share your codes for the example problems using this technique.
•  » » 8 months ago, # ^ |   +15 This is my code for the problem suggested by mahmud2690 BDOI16E. It combines two techniques as discussed above. codevoid dfs(int p, int u) { for(auto v : G[u]) { if(v != p) { dfs(u, v); } } // init F[u] = 0; // merge for(auto v : G[u]) { if(v != p) { // Sum joy gain to child set F[v] += jplus[v]; // Small-to-Large technique if(joys[u].size() < joys[v].size()) { swap(joys[u], joys[v]); swap(F[u], F[v]); } // Applying venice technique on merge for(auto val : joys[v]) { ll nval = val + F[v]; joys[u].insert(nval - F[u]); } } } // Insert root joys[u].insert(J[u] - F[u]); // ans ans[u] = joys[u].size(); }
•  » » » 8 months ago, # ^ |   0 Thanks :)
•  » » 8 months ago, # ^ |   +2 This is my code for the other problem suggested by Omar_Elawady. Although the hardest part is getting the mex. Solutionstruct MexTrie { struct Node { Node* child[2]; int cnt; Node(): cnt(0) { child[0] = child[1] = NULL; } }; Node *root; MexTrie() { root = new Node(); } void insert(int x) { if (exists(x)) return; Node *v = root; v->cnt++; for (int i = 30; i >= 0; --i) { int b = (x >> i) & 1; if (v->child[b] == NULL) v->child[b] = new Node(); v = v->child[b]; v->cnt++; } } bool exists(int x){ Node *v = root; for (int i = 30; i >= 0; --i) { int b = (x >> i) & 1; if (v->child[b] == NULL) return false; v = v->child[b]; } return true; } int mex(int x) const { Node *v = root; int m = 0; for (int i = 30; i >= 0; --i) { int b = (x >> i) & 1; if (v->child[b] == NULL) return m; if (v->child[b]->cnt == (1<child[b] == NULL) return m; v = v->child[b]; } // should never reach here assert(false); } }; struct VeniceSet { int globalX = 0; MexTrie T; void insert(int x) { T.insert(x); } void xorAll(int x) { globalX ^= x; } int getMex() { return T.mex(globalX); } }; `
•  » » » 8 months ago, # ^ |   0 Thanks :)