Introduction to Range Query Problems [C++]

Revision en6, by Jellyman102, 2020-06-22 23:37:50

Author's Disclaimer: The following content is targeted towards those who are unfamiliar with range queries and how they work. If you are familiar with BITs, segment trees, and prefix sums, you will likely not learn anything new from reading this.

Author's Disclaimer #2: This is my first blog in a series of blogs I plan on writing that introduce various types of problems to beginner competitive programmers. That being said, I am by definition a beginner myself (regardless of my rating or competitive math experience, I have been doing this for less than a year). If you have any suggestions on how these could be improved, don't be afraid to speak up.

Note: Whenever I ask "why?" in parenthesis, this is not me asking because I don't know. This is me encouraging you to stop and think through why something I said is true. I don't want to just give answers, I want to provoke thought. This is how we learn. If you're stuck, feel free to ask in the comments.

Basic Sum Queries (Prefix Sums)

Let's say we have some array $$$A$$$ = $$$A_{1}$$$, $$$A_{2}$$$, ..., $$$A_{n}$$$. Given two indices $$$i$$$ and $$$j$$$, we are tasked to find the following sum.

$$$\sum\limits_{k=i}^{j} A_{k}$$$

For those unfamiliar with the notation, this is simply $$$A_{i} + A_{i+1} + ... + A_{j}$$$.

We could do this by iterating over each element and adding it to a sum which is initially 0. The complexity of this is $$$O(n)$$$ (why?), which is too slow if we are processing a bunch of these queries.

Instead, we can generate some useful information about each index in $$$O(n)$$$ and then solve each query in $$$O(1)$$$. Let $$$dp_{i} = \sum\limits_{k=0}^{i} A_{k}$$$. Thus, $$$\sum\limits_{k=i}^{j} A_{k} = dp_{j} - dp_{i-1}$$$. Watch the $$$i=0$$$ case!

These $$$dp$$$ values can be stored in another array (or you can change the original array if you're feeling edgy that day and the problem allows it).

Note: This is technically really simple dp, but I'm in a small minority by actually notating it this way. Most people put psums in a different category.

This is the cses problem that correlates with this skill: https://cses.fi/problemset/task/1646

Next, try using prefix sums to solve this: 466C - Number of Ways

Sum Queries with a BIT

Let's say we have the same task but an extra challenge is added. A new type of query is introduced in which we must add some value to one of the elements in the array. If we were to keep using the prefix sum method, suddenly we would have to rebuild the $$$dp$$$ array each time this type of query is called upon (why?). This is where a binary indexed tree (also known as a Fenwick tree) comes in. This uses bit operations (more precisely, powers of 2) to solve both types of queries in $$$O(\log n)$$$.

The main idea behind easily implementing this is that the largest power of two that divides some integer $$$k$$$ is k&(-k) (why?). We'll notate the largest power of two that divides $$$k$$$ as $$$☺(k)$$$ (this is obviously not official notation, please don't use it elsewhere or people will laugh at you). We then build a new array (we'll call it $$$T$$$ for tree) such that $$$T_{k}$$$ contains the sum of all elements in the sub-array that is of length $$$☺(k)$$$ and ends at index k.

To compute $$$\sum\limits_{i=0}^{k} A_{k}$$$, let $$$j = k$$$. Then, while(j > 0){ sum += T[j]; j -= j&(-j); }. As an exercise for the reader, try to think about how updating a value would work.

Hint

Both of these operations occur in $$$O(\log n)$$$ (why?).

This is a very confusing topic. Here is a diagram that may help (pulled from the cses handbook and edited for generalization purposes). This is also a good reminder to NOT make your BITs 0-based!

This is the cses problem that correlates with this skill: https://cses.fi/problemset/task/1648

Next, try to use a BIT to find the amount of inversions in an array. Don't be discouraged, this may be challenging! An inversion is a pair of indices $$$i < j$$$ such that $$$A_{i} > A{j}$$$.

Segment Trees (Iterative Implementation)

Tags #bit, #segment tree, #range query, #c++, #beginner, prefix sum, #math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en17 English Jellyman102 2020-06-23 01:30:06 332
en16 English Jellyman102 2020-06-23 00:36:16 0 (published)
en15 English Jellyman102 2020-06-23 00:32:28 154
en14 English Jellyman102 2020-06-23 00:31:18 123
en13 English Jellyman102 2020-06-23 00:29:17 5 Tiny change: 'your BITs 0-based!\n\' -> 'your BITs zero-based!\n\'
en12 English Jellyman102 2020-06-23 00:27:14 9 Tiny change: 'or reading thus far. Happy co' -> 'or reading. Happy co'
en11 English Jellyman102 2020-06-23 00:26:24 9 Tiny change: 'ng a blog about this sinc' -> 'ng a blog like this sinc'
en10 English Jellyman102 2020-06-23 00:25:42 134
en9 English Jellyman102 2020-06-23 00:23:26 153
en8 English Jellyman102 2020-06-23 00:18:53 2446
en7 English Jellyman102 2020-06-23 00:01:27 1668
en6 English Jellyman102 2020-06-22 23:37:50 20
en5 English Jellyman102 2020-06-22 23:36:53 288
en4 English Jellyman102 2020-06-22 23:23:05 68 Tiny change: 'exed tree comes in.' -> 'exed tree (also known as a Fenwick tree) comes in.'
en3 English Jellyman102 2020-06-22 23:04:30 978
en2 English Jellyman102 2020-06-22 20:18:35 1960 Tiny change: 'p_{j} - dp{i-1}$. ' -> 'p_{j} - dp_{i-1}$. '
en1 English Jellyman102 2020-06-22 19:50:46 925 Initial revision (saved to drafts)