Choppy Arrays Continued
Continued from post on BITS.
The choppy array, which only stores benchmarks.Only storing benchmarks allow a roughly O(n/x+x) speedup to commands.
Adding a element. Mark each index in the details up to the next benchmark.
Only some things are stored!
Example
First, let's increment index 2. Here, 2,3,4,5,6,7,8,9 are all incremented. Then, only the benchmarks are incremented (10,20,30,40).
We can think of it like this: The 2,3,4, and 5 represent a small stream, where at 9 the stream merges into a river only containing benchmarks. So we can imagine a choppy tree/array like so:
0~~~~~~~~~~~~~~10~~~~~~~~~~~~~~~~~~~20~~~~~~~~~~~~~~~~~~~30
/ / /
1~2~3~~~~~8~9~ 11~12~13~~~~~18~19~ 21~22~23~~~~~28~29~
We increment 2 to 9, then 10, 20 and 30:
0~~~~~~~~~~~~~~~1~~~~~~~~~~~~~~~1~~~~~~~~~~~~~~~1
/ / /
0~1~1~~~~~1~1~ 0~0~0~~~~~0~0~ 0~0~0~~~~~0~0~
Notice how 11 is not changed. A boat can only row downstream, not upstream.
Let's do the same for 13.
0~~~~~~~~~~~~~~~1~~~~~~~~~~~~~~~2~~~~~~~~~~~~~~~2
/ / /
0~1~1~~~~~1~1~ 0~0~1~~~~~1~1~ 0~0~0~~~~~0~0~
As before, notice how the third stream is not changed!
To query, we take the corresponding index in the current STREAM and sum it with the last benchmark in the RIVER. For example, querying 11:
The value in the stream is 0, and the value of 10 in the river is 1. So, the sum is 1.
Let's try 15.
The value in the stream is 1. and the value of 10 in the river is 1. So, the sum is 2.
Last but not least, let's try 22.
The value in the stream is 0. and the value of 20 in the river is 2. So, the sum is 2.
https://www.dropbox.com/s/fi2tam6zxwats08/5JR%284WMDHG%5DC2ZQ%607E%292_5U.png?dl=0 Adding a element.
https://www.dropbox.com/s/g55gtlb3ff6hlr0/%25P9%7DP%5B0S07J%2596~K%5BGZ%5DVME.png?dl=0 Only some things are stored!
The choppy array, which only stores benchmarks.Only storing benchmarks allow a roughly O(n/x+x) speedup to commands.
Adding a element. Mark each index in the details up to the next benchmark.
Only some things are stored!
Example
First, let's increment index 2. Here, 2,3,4,5,6,7,8,9 are all incremented. Then, only the benchmarks are incremented (10,20,30,40).
We can think of it like this: The 2,3,4, and 5 represent a small stream, where at 9 the stream merges into a river only containing benchmarks. So we can imagine a choppy tree/array like so:
0~~~~~~~~~~~~~~10~~~~~~~~~~~~~~~~~~~20~~~~~~~~~~~~~~~~~~~30
/ / /
1~2~3~~~~~8~9~ 11~12~13~~~~~18~19~ 21~22~23~~~~~28~29~
We increment 2 to 9, then 10, 20 and 30:
0~~~~~~~~~~~~~~~1~~~~~~~~~~~~~~~1~~~~~~~~~~~~~~~1
/ / /
0~1~1~~~~~1~1~ 0~0~0~~~~~0~0~ 0~0~0~~~~~0~0~
Notice how 11 is not changed. A boat can only row downstream, not upstream.
Let's do the same for 13.
0~~~~~~~~~~~~~~~1~~~~~~~~~~~~~~~2~~~~~~~~~~~~~~~2
/ / /
0~1~1~~~~~1~1~ 0~0~1~~~~~1~1~ 0~0~0~~~~~0~0~
As before, notice how the third stream is not changed!
To query, we take the corresponding index in the current STREAM and sum it with the last benchmark in the RIVER. For example, querying 11:
The value in the stream is 0, and the value of 10 in the river is 1. So, the sum is 1.
Let's try 15.
The value in the stream is 1. and the value of 10 in the river is 1. So, the sum is 2.
Last but not least, let's try 22.
The value in the stream is 0. and the value of 20 in the river is 2. So, the sum is 2.
Images
https://www.dropbox.com/s/c58b83gxgy69jhw/4TG19K%28_8%28AOAB%5B%248%29WBACL.png?dl=0 The choppy array.https://www.dropbox.com/s/fi2tam6zxwats08/5JR%284WMDHG%5DC2ZQ%607E%292_5U.png?dl=0 Adding a element.
https://www.dropbox.com/s/g55gtlb3ff6hlr0/%25P9%7DP%5B0S07J%2596~K%5BGZ%5DVME.png?dl=0 Only some things are stored!
Comments
Post a Comment