- Wavelet tree - Mergesort tree - Binomial heap - Fibonacci heap - Leftist heap, tree except treap - Link-cut tree - Wavelet tree - Mergesort tree - Binomial
heap
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
Things I don't know I'm just in a mood to shitpost. Don't take it too seriously.
Things that I have heard of, but don't know (imagine how many things I haven't even heard of):
- Li-Chao Segment Tree
- Segment Tree Beats
- RMQ in $O(n)$/$O(1)$
- Any self-balancing tree except treap
- Link-cut tree
- Wavelet tree
- Mergesort tree
- Binomial heap
- Fibonacci heap
- Leftist heap
- Dominator tree
- 3-connected components in $O(n)$
- $k$-th shortest path
- Matching in general graph
- Weighted matching in general graph
- Preflow-push
- MCMF in $O(poly(V, E))$
- Minimum arborescence (directed MST) in $O(E \log V)$
- Suffix tree
- Online convex hull in 2D
- Convex hull in 3D
- Halfplane intersection
- Voronoi diagram / Delaunay triangulation
- Operation on formal power series (exp, log, sqrt, ...) (I know the general idea of Newton method)
- How to actually use generating functions to solve problems
- Lagrange Inversion formula
- [...
2.
I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3>
# Mathematics Stuff
- [Number Theory in Competitive Programming [Tutorial]](https://codeforces.me/blog/entry/46620)
- [Number of points on Convex hull with lattice points](https://codeforces.me/blog/entry/62183)
- [FFT, big modulos, precision errors.](https://codeforces.me/blog/entry/48465)
- [Number of ways between two vertices](https://codeforces.me/blog/entry/19078)
- [Mathematics For Competitive Programming](https://codeforces.me/blog/entry/76938)
- [FFT and NTT](https://codeforces.me/blog/entry/19862)
- [Burnside Lemma](https://codeforces.me/blog/entry/51272)
- [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.me/blog/entry/76836)
- [On burnside (again)](https://codeforces.me/blog/entry/64860)
- [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.me/blog/entry/55912)
- [Probabili...
Directed Tree](https://codeforces.me/blog/entry/75627) - [Wavelet Tree
Problems](https, /blog/entry/75627) - [Wavelet Tree
Problems](https://codeforces.me/blog/entry/70363
3.
Introduction to New Data Structure: Wavelet Trees Hi CF Community,
http://rachitiitr.blogspot.in/2017/06/wavelet-trees-wavelet-trees-editorial.html
I think it's safe to assume that this is a new data structure for most of us.
Consider the following problems:
1. Number of elements in subarray $A[L...R]$ that are less than or equal to $y$.
(Persistence Segment Tree? Ordered multiset + BIT ?)
2. Number of occurrences of element $x$ in subarray $A[L...R]$.
(Subpart of 1st problem)
3. The $k^{th}$ smallest element in subarray $A[L...R]$.
(Ordered multiset + BIT would work for subarrays beginning from index 1)
I know you might have many other solutions, and you might think what I am trying to prove.
What if I told you, all of the above can be easily done in O(logn) using Wavelet Trees :o. Plus, its very easy to code :D Awesome, isn't it?
Check the implementation [here](http://ideone.com/Tkters).
The post just introduces the basic usage of wavelet trees. There is still more that you can ...
Introduction to New Data Structure: Wavelet Trees, $. (Persistence Segment Tree? Ordered multiset + BIT ?) 2. Number of
occurrences of element $x, Hi CF Community, http://rachitiitr.blogspot.in/2017/06/wavelet-trees-wavelet
-trees, The post just introduces the basic usage of wavelet trees. There is still more
that you can do with, What if I told you, all of the above can be easily done in O(logn) using Wavelet
Trees :o. Plus, http://rachitiitr.blogspot.in/2017/06/wavelet-trees-wavelet-trees-editorial.html
4.
[Tutorial] Another way to look at the segment tree and many other data structures I haven't seen anyone to write about this technique, so I decided to make a blog about it. I know that it is mostly general intuition, but not everyone really understand it. Also, I would be happy if you add something in comments or correct some errors. Also, before reading this blog I recommend to have some knowledge about segment tree and divide and conquer.
I would like to thank [user:riazhskkh,2024-08-17] and [user:FBI,2024-08-17] for reviewing this blog.
### **The main idea**
When we have some divide and conquer algorithm, we can memorize each recursive call to be able to operate with it as data structure. For example, when we do merge sort, we can memorize how array looked after sorting on each call. Using this we can get merge sort tree. Also, if we memorize quick sort in such way, we will get wavelet tree. A lot of standart ways to use divide and conquer would lead to segment tree. But, it also can be used when we divide array on 3 parts or more, when we divide consideri...
[Tutorial] Another way to look at the segment tree and many other data
structures, such way, we will get wavelet tree. A lot of standart ways to use divide and
conquer would lead to, , if we memorize quick sort in such way, we will get wavelet tree. A lot of
standart ways to use divide
5.
All the good tutorials found for Competitive Programming Here is the list of some of the good tutorials written by codeforces users :-
**C++**
- [C++ Tricks](http://codeforces.me/blog/entry/15643) by [user:Swift,2018-01-22]
- [C++ STL: map and set](http://codeforces.me/blog/entry/9702) by [user:adamant,2018-01-24]
- [C++ STL: Policy based data structures](http://codeforces.me/blog/entry/11080) by [user:adamant,2018-03-05]
- [Competitive C++ Manifesto: A Style Guide](https://codeforces.me/blog/entry/64218) by [user:Swift,2019-03-04]
- [Catching silly mistakes with GCC](https://codeforces.me/blog/entry/15547) by [user:andreyv,2019-03-04]
- [About a general reader / writer for STL-Structures,](https://codeforces.me/blog/entry/71075) by [user:Arturgo,2020-12-20]
- [Blowing up unordered_map, and how to stop getting hacked on it](https://codeforces.me/blog/entry/62393) by [user:neal,2020-12-20]
- [C++ tips and tricks](https://codeforces.me/...
introduction to "Segment tree beats"](http://codeforces.me/blog/entry/57319)
by [user:jiry_2,2018, tree beats"](http://codeforces.me/blog/entry/57319) by
[user:jiry_2,2018-01-24] - [Sack(DSU on
6.
Is Wavelet Tree Actually Useless? When I was in high school I once learned about wavelet tree and I was really impressed. But over time when I learned more tricks I started thinking: is there any essential need in it? Because it seems like merge-sort tree with fractional cascading solves all the same problems and its time complexity is $O(\log n)$ which is better than $O(\log C)$.
So, am I right or not? Does anyone know any cases where it's helpful to use wavelet tree?
Is Wavelet Tree Actually Useless?, So, am I right or not? Does anyone know any cases where it's helpful to use
wavelet tree?, When I was in high school I once learned about wavelet tree and I was really
impressed. But over
7.
Getting Runtime Error in SPOJ K-th Number (MKTHNUM) with Wavelet Tree I've been trying to solve this problem with wavelet tree, and optimize by discrete the values from $[-10^9, 10^9]$ to $[0, N - 1]$. I keep getting runtime error.
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
struct splitmix64_hash {
static unsigned long long splitmix64(unsigned long long x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
unsigned long long operator()(unsigned long long x) const {
static const unsigned long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<class T, class U, class H = splitmix64_hash> using hash_map = gp_hash_table<T, U, H>;
template<class T, class H = splitmix64_hash> using hash_set = hash_map<T, null_type, H>;
template<class T>
class wavelet {
...
Getting Runtime Error in SPOJ K-th Number (MKTHNUM) with Wavelet Tree, = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin(); mp[id] = a[i]; a[i] =
id; }wavelet, I've been trying to solve this problem with wavelet tree, and optimize by
discrete the values from, private: T low, high; wavelet* l; wavelet* r; vector a; };, template class wavelet { public: wavelet(T* from, T* to, T L, T R) : low(L),
high(R, ~wavelet() { delete l; delete r; }
8.
Wavelet Tree Implementation(Array Based) I recently learned wavelet trees. This data structure can handle the following types of range queries in logarithmic time:
1. Number of elements in subarray A[L...R] that are less than or equal to y.
2. Number of occurrences of element x in subarray A[L...R].
3. The kth smallest element in subarray A[L...R].
But I couldn't find the array based implementation of it anywhere, and as I don't like pointers(also pointer based implementations are often slower than array based ones because of the dynamic memory allocation), I implemented it myself. Here is the implementation: https://github.com/thisIsMorningstar/Competitive_Programming/blob/main/templates/wavelet_tree.cpp
I stress tested this with a bruteforce code against a couple thousand random testcases and it passed. But if you find any bugs in it, do let me know :).
You can learn about wavelet trees from here: https://codeforces.me/blog/entry/52854
Wavelet Tree Implementation(Array Based), I recently learned wavelet trees. This data structure can handle the following
types of range, You can learn about wavelet trees from here:
https://codeforces.me/blog/entry/52854
9.
IOI preparation lectures and contests I conducted a camp for Kazakhstan via the Internet and I was allowed to record it. I'm putting some of those lectures and problem analysis on Youtube. Maybe it will be useful for participants who are still practicing. See recent videos here, [https://www.youtube.com/errichto2](https://www.youtube.com/errichto2).
There are currently solutions for Innopolis Open 2018-19 (cool hard contest in CF GYM), two days of POI 23 (2015-2016) and also a lecture on wavelet trees. Innopolis Open solutions include these two methods:
<spoiler summary="">
Sum over subset (SOS) and Halfplanes intersection
</spoiler>
Will soon add some more, including segment tree beats and Li Chao tree.
GYM), two days of POI 23 (2015-2016) and also a lecture on wavelet trees.
Innopolis Open solutions, POI 23 (2015-2016) and also a lecture on wavelet trees. Innopolis Open
solutions include these two
10.
[Tutorial] Kruskal Reconstruction Tree Hello CodeForces!
Instead of posting a not-so-meaningful blog that helps farm my contribution, today, I would like to have the CodeForces community being benefited at the same time. Therefore, I would like to make a blog about one of my favourite techniques applied on trees, the Kruskal Reconstruction Tree. Although this technique is not too commonly used in CodeForces rounds, it has become more and more popular in other competitions such as the IOI. Also, I found out that there are some very limited resources about this technique that is written in English. Therefore, I would like to write a blog on KRT. **If you find this blog useful, please DOWNVOTE this blog.** It will give me immense support to do other topics like these in the future.
#Prerequisites:
Finding MST by using Kruskal's Algorithm
Disjoint Set Union
Finding lowest common ancestor in $O(n log n)$ precomputation time and $O(log n)$ for each query.
#Problem:
Given a graph with $N$ nodes and $M$ weighte...
[Tutorial] Kruskal Reconstruction Tree, common. This can be efficiently computed by either a binary indexed tree or a
wavelet tree in $O(n, computed by either a binary indexed tree or a wavelet tree in $O(n log n)$
precomputation and $O(log
11.
Solving 894D for arbitrary trees in O(nlog^2n) This article is about a solution to a variation of [problem:894D], with (almost) complete binary trees replaced by arbitrary trees. The solution turned out to be more complicated than I thought, so I decided to post it as a separate blog.
The main idea is to fix the LCA, just like the original problem.
Note: We are calculating the sum of all $H_i - L$, such that $$H_i - L \geq 0 \iff H_i - (d_{A_i} + d_x - 2d_{lca(A_i,x)}) \geq 0 \iff H_i - d_{A_i} + 2d_{lca(A_i,x)} \geq d_x \iff d_x \leq H_i - d_{A_i} + 2d_{lca(A_i,x)}$$
where $x$ is any destination vertex and $d_v$ is the distance from the root to the $v$-th vertex.
Therefore, we could calculate the answer using the following functions:
~~~~~
// dist[v] = sorted list of d_x, where x is any node in v's subtree
// prefsum[v] = prefix sum array of dist[v]
typedef long long i64;
i64 helper(int v, i64 val) {
if(v == 0) return 0;
auto x = std::upper_bound(dist[v].begin(), dist[v].end(), val);
if(x == dist[v].be...
that $a_i \leq x$. We can use a wavelet tree/persistent segment tree/simple
segmenttree (offline, ] such that $a_i \leq x$. We can use a wavelet tree/persistent segment tree
/simple segmenttree
12.
Help me with this data structure problem pls! Given an array A of size n. Do these q queries:
1 pos x: assign A[pos] = x;
2 l r k: find k-th smallest element in range [l,r]
Constraints:
n,q <= 1e5
A[i], x <= 1e9
My first aproach was to use a Wavelet tree with a BST(specifically a Treap) on each of its nodes. This gives a time complexity of O(n*log^2) and can do online queries(I still did it offline, i had to read all the input and compress the values because i don't want to make the Wavelet tree dynamic). However it has a really high constant factor and it takes 7-8 seconds to run with the full constraints.
Here's my code if you're interested (sorry if it's poorly written):
<spoiler summary="My Code">
```c++
#include <bits/stdc++.h>
using namespace std;
//#define int long long //emergency debug
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define hellnah cout<<"NO\n"
#define fuckyea...
aproach was to use a Wavelet tree with a BST(specifically a Treap) on each of
its nodes. This gives a, My first aproach was to use a Wavelet tree with a BST(specifically a Treap) on
each of its nodes
13.
What updates are available to a wavelet tree? Usually the wavelet tree is made not to support updates. I wonder what types of updates it can recieve that will still keep all its operations in $O(\log{}A)$, where $A$ is the range of values it gets. For instance the only one I found is that you can support appending or removing the element from the back of the array (on which the wavelet is built).
A short tutorial for this data structure can be found [here](http://codeforces.me/blog/entry/52854), for those who are interested.
What updates are available to a wavelet tree?, Usually the wavelet tree is made not to support updates. I wonder what types of
updates it can
14.
Wavelet tree problems Hey Codeforces community,
have you ever seen any problems that use Wavelet Tree/Matrix or can be solved using these data structures?
Problems created especially for these structures don't count (for example they should appear in some competition).
Wavelet tree problems, Hey Codeforces community, have you ever seen any problems that use Wavelet Tree
/Matrix or can be, have you ever seen any problems that use Wavelet Tree/Matrix or can be solved
using these data
15.
[Video Tutorial] Introduction to Wavelet Trees: Simple, Clean Yet Powerful Hi everybody,
If you can recall, I had written a tutorial for a relatively new Data Structure: Wavelet Trees.
The link to that post is [here](http://codeforces.me/blog/entry/52854).
I have made a video tutorial for the same. Check out the video here.
[Tutorial — Wavelet Trees | Introduction to New Data Structure](https://www.youtube.com/watch?v=K7tju9j7UWU)
Happy Coding!
[Video Tutorial] Introduction to Wavelet Trees: Simple, Clean Yet Powerful, : Wavelet Trees. The link to that post is
[here](http://codeforces.me/blog/entry/52854, I have made a video tutorial for the same. Check out the video here. [Tutorial —
Wavelet, If you can recall, I had written a tutorial for a relatively new Data Structure:
Wavelet Trees
16.
Things I don't know (Master edition) In last contest I finally achieved Master. It still feels a bit surreal to see the orange next to my name after so many contests and late nights.
This blog is inspired by [user:reirugan,2025-04-04] [blog](https://codeforces.me/blog/entry/141214). So I decided to write something similar — a list of things I still don’t know.
- Every single thing in [this list](https://codeforces.me/blog/entry/92248) except $ \downarrow $
- Li-Chao Segment Tree
- Segment Tree Beats
- RMQ in $ O(n)/O(1) $
- Wavelet tree
- Mergesort tree
Becoming Master doesn’t really require knowing super advanced or obscure algorithms. You just need to keep solving problems, learning from them, and being consistent.
(Like my Brother said: You become BoxMaster XD)
- Wavelet tree
17.
Wavelet Tree Swap Function Implementation I´m having a hard time implementing the swap function for a wavelet tree, which would be:
*Given an index $i$, swap the elements at positions $i$ and $i + 1$.*
Can anyone point any references that would help?
Wavelet Tree Swap Function Implementation, I´m having a hard time implementing the swap function for a wavelet tree, which
would be:
18.
New data structures Hello everyone,
I've found couple of interesting data structures recently, e.g:
Palindromic tree — http://adilet.org/blog/25-09-14/ ,<br>
http://codeforces.me/blog/entry/13959 (thanks to [user:adamant,2015-05-08])
and Wavelet Matrix — http://www.dcc.uchile.cl/~gnavarro/ps/spire12.4.pdf
([user:anta,2015-05-08] used it in problem E in last round — http://codeforces.me/contest/543/submission/11036065 )
It made me wonder, how many great and useful, less known data structures are out there?
This is a question for you — do you know any?
Please share them with us.
Greetings
tree — http://adilet.org/blog/25-09-14/ ,
http://codeforces.me/blog/entry/13959 (thanks
19.
Runtime Error on SPOJ only I'm trying to solve [MKTHNUM](http://www.spoj.com/problems/MKTHNUM/) on SPOJ using Wavelet Tree Data structures from [rachitjain's blog](http://codeforces.me/blog/entry/52854)
Here is my code: http://ideone.com/BMZqj0
Unfortunately, I keep getting RTE on large test cases.
However, I have also tested my solution on [this problem](https://pandaoj.com/problem/INC2015H) with the exact same [code](http://ideone.com/U2977W) (only differs in use of test cases) and it got accepted on that problem.
Can anyone tell why my solution getting RTE on SPOJ while getting accepted on other OJ?
P.S. I also got RTE on [KQUERY](http://www.spoj.com/problems/KQUERY/) problem using the same data structure.
Thanks.
I'm trying to solve [MKTHNUM](http://www.spoj.com/problems/MKTHNUM/) on SPOJ
usingWavelet Tree
20.
Help wanted: Wavelet tree Hey, I want to solve this problem: Given array a of length n handle these queries (each query in O(logn))
-> l r k (input) which means output the sum of k largest numbers on segment [l,r] in array a.
($n <= 10^6$ , $q <= 10^6$ (q is number of queries), the array has only positive integers ($a_i <= 10^9$))
I know it is possible to do using Wavelet tree.
Help wanted: Wavelet tree, I know it is possible to do using Wavelet tree.
21.
the reason why most of you aren't red... # so it seems like many people are struggling to be red
##I THINK THIS because you cant even write code
learn from the true red, this is how we write code https://codeforces.me/contest/4/submission/203467882
also people like Um_nik cant even be 1st because like they dont even know wavelet tree??? like it is so easy just make a tree
also a lot of people struggle to get to **YELLOW** which is the _easiest_ rate to achieve,, because they write recursive segmant tree?? honestly go learn how to code...
/submission/203467882 also people like Um_nik cant even be 1st because like
they dont even knowwavelet, also people like Um_nik cant even be 1st because like they dont even know
wavelet tree??? like it
22.
[HELP] Sum of K-largest numbers in a range (using Merge Sort Tree?) I was wondering if it's possible to use **Merge Sort Tree** to find out the sum of K-largest numbers in a range. I've seen people solve it using **Wavelet tree** and **Persistent Segment Tree**. I failed to implement **Merge Sort Tree** in such a way that it solves the given task and now wondering if it's possible to do so.
[HELP] Sum of K-largest numbers in a range (using Merge Sort Tree?), numbers in a range. I've seen people solve it using **Wavelet tree** and
**Persistent SegmentTree**. I
23.
Hints/Solutions for Kattis: Easy Query? Recently, I came across [this](https://open.kattis.com/problems/easyquery) problem through the [USACO Guide](https://codeforces.me/blog/entry/80438) (thanks [user:Benq,2020-07-28], [user:thecodingwizard,2020-07-28], [user:caoash,2020-07-28], [user:darren_yao,2020-07-28], [user:nchn27,2020-07-28], and [user:frodakcin,2020-07-28] for the the amazing resource!).
I know (from the guide) that the solution involves Wavelet Trees, I have no idea how to use it here (actually, I really only understand the basic implementation).
Any hint/solution/approach is greatly appreciated.
Thanks.
Edit: I couldn't find any editorials online either, the closest I found was [this](https://codeforces.me/blog/entry/72047). The problem comes from the 2019 ICPC Asia Danang Regional Contest (Problem E).
solution involves Wavelet Trees, I have no idea how to use it here (actually,
I really only, I know (from the guide) that the solution involves Wavelet Trees, I have no
idea how to use it here
24.
Wavelet tree and update query is wavelet tree has update query and what update query support for wavelet tree ( such change value of an element( point update ) ). Thank for your answear
Wavelet tree and update query, is wavelet tree has update query and what update query support for wavelet tree
( such change
25.
plz help me in my last blog a guy told me this:
```
The list of topics that you should learn for solving 800 rated problems : Li-Chao Segment Tree
Segment Tree Beats
RMQ in O(n)/O(1)
Any self-balancing tree except treap
Link-cut tree
Wavelet tree
Mergesort tree
Binomial heap
Fibonacci heap
Leftist heap
Dominator tree
3-connected components in O(n)
k-th shortest path
Matching in general graph Weighted matching in general graph Preflow-push
MCMF in O(poly(V,E))
Minimum arborescence (directed MST) in O(ElogV)
Suffix tree
Online convex hull in 2D
Convex hull in 3D
Halfplane intersection
Voronoi diagram / Delaunay triangulation
Operation on formal power series (exp, log, sqrt, ...) (I know the general idea of Newton method)
How to actually use generating functions to solve problems
Lagrange Inversion formula
```
can it be as hard as this to solve 800 rated problems?is he joking?
plz help me!!!!!
Segment Tree Beats RMQ in O(n)/O(1) Any self-balancing tree except treap
Link-cuttree Wavelet, tree except treap Link-cut tree Wavelet tree Mergesort tree Binomial heap
Fibonacci heap Leftist
26.
Wavelet Tree Implementation Hello codeforces community,
Is there anyone who has proper implementation of wavelet tree? I am having a hard time coding it.
I tried using the code mentioned below but its giving runtime error.
Code — https://ideone.com/Tkters
Wavelet Tree Implementation, Hello codeforces community, Is there anyone who has proper implementation of
wavelet tree? I am, Is there anyone who has proper implementation of wavelet tree? I am having a
hard time coding it.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/23/2026 12:50:55 (g2).
Desktop version, switch to mobile version.
Supported by
