You already know arrays: contiguous memory, access by index, search. I won't rehash basics. What you might not know is how to exploit array structure for speed.
The next technique I'll show you turns range queries into . That's not a typo.
One million queries on a million elements goes from a trillion operations to just one million. How? By precomputing the right information.