Large and small comparison with many things → Fennic tree

I want to know the number of items that satisfy the condition by comparing the size of N items and the number of items that satisfy the condition.

O(N) when large and small comparisons are made for each one. However, O(NQ) is sometimes too slow, especially in cases where many queries are issued.

If we put N things in the Fennic tree, we can get the number of things that satisfy the condition in logarithmic order by taking the range sum

• Make a value range a definite range

• Lots of queries matter.

---

This page is auto-translated from /nishio/多くのものと大小比較→フェニック木 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.