I really like data structures, so here I’ll present 2 not really well-known tricks:

**1.** Have you heard about the problem with queries: add X( \leq 10^{18}) to the set and find the sum of all elements between L and R?

It sounds difficult and one may think about the treaps / C++ ordered sets / implicit segment trees and so on…

But there is an amazing and simple solution with… **TRIE!!**

Yes, observe that sum(L, R) = sum(0, R) - sum(0, L - 1).

Do you see how the Trie can be used?

**2.** Everyone knows that segment-tree has depth O(log N) and SQRT-decomposition has the depth = 2, but have you ever thought about hybrid data structure, for example 3-level sqrt decomposition, the array divided into N^\frac{1}{3} continuous sub-arrays and each that sub-array is divided into N^\frac{1}{3} continuous sub-arrays. The update will go in O(depth), but the query of sum on sub-segment will processed in O(N^\frac{1}{depth}).

**3.** Imagine you have the fixed pairing (in scenario of maximal matching). How quickly you can add/remove edges and recalculate the value of the maximal pairing?

P.S. I̶ ̶w̶o̶u̶l̶d̶ ̶l̶i̶k̶e̶ ̶t̶o̶ ̶i̶n̶v̶i̶t̶e̶ ̶t̶h̶e̶ ̶b̶e̶s̶t̶ ̶a̶n̶d̶ ̶t̶h̶e̶ ̶s̶w̶e̶e̶t̶t̶i̶e̶s̶t̶t̶t̶t̶ ̶a̶d̶m̶i̶n̶ ̶o̶f̶ ̶c̶o̶d̶e̶c̶h̶e̶f̶ ̶@̶v̶i̶j̶j̶u̶1̶2̶3̶ ̶t̶o̶ ̶e̶d̶i̶t̶ ̶t̶h̶e̶ ̶b̶l̶o̶g̶ @vijju123 your turn