Dynamic Binary Indexed Tree

Dynamic Binary Indexed Trees

Here we go,

Problem Statement:

You are given an integer N, size of the array initialized to 0, and Q queries.

queries are of 2 types.

1. update value V at index I.

2. Output the sum of element <=Index I.

Queries are given in the format

1 I V

2 I

Constraint: 

1<=N<=10^18

1<=Q<=10^5

all queries are online
I=(previous_answer+I)%N+1
V=(previous_answer+V)%N+1

Solution Approach:

Why do we need Dynamic BIT?
Let's solve the problem bit by bit.
If constraints were low then we can use a simple Segment tree or Fenwick tree for this purpose.
If queries weren't asked in an online manner then we can use coordinate compression and make the BIT of at most 10^5 size as that will cover all the queries.

But if constraints are high and the problem isn't offline.
Here comes the Idea of "Dynamic Binary Indexed Tree".
We can solve this by Dynamic Segment Trees to but for the sake of this article, we are going to stick with the idea of BIT.

It is not a new Data Structure, just a new Implementation of previous data structures.
here, in our case, it is TRIES.
Yes, We are going to implement Seg Trees with Tries.
It is actually simpler to implement than regular Dynamic Seg trees.
Now as in the Problem statement maximum length of a number can be 10^18.
so our Trie will go 18 levels deep.

Each node of a Trie will have 2 arrays of size 10.
1st array will contain the value. Let's call this array of values (initialized to 0).
2nd array will contain a pointer to the next node. Let's call this array of pointers (initialized to null).


Like Dynamic Seg Trees, we will use the lazy concept here.
"Create the node only when you need them."

Algorithm 1:
Inserting a value V at an index NUM.

Steps:
1. Start with the MSB and go towards LSB. as we are using tries, convert each number to a string and make its length equal to 18 by inserting 0's in front of the number.
2. Start with the root node and 18th digit of the number, if there is no node at the current digit's pointer array create a node. If there is one just traverse that node.
3. Repeat step 2 for each digit until you reach the last digit.
4. At the last digit store the value V in the respective digit's index in the value array of that node.
while coming up from recursion. put the sum of all the values from 1 to 9 of the value array of its children at that digit's value array.
5. Repeat step 4 until you come out of recursion.

Algorithm 2:
Querying for an index NUM.

Steps:
1. Start with the MSB and go towards LSB. as we are using tries, convert each number to a string and make its length equal to 18 by inserting 0's in front of the number.
2. Start with the root node and 18th digit of the number, if there is no node at the current digit's pointer array return ( 0 + value at that node's digit place in the value array ). If there is one just traverse that node.
3. Repeat step 2 for each digit until you reach the last digit or you get a NULL in the pointer array, let's call this point the stopping point.
4. At the stopping point take the sum of all values from 0 until that digit and return the sum of the values.
5. Repeat step 4 until you come out of recursion.

That is some basic idea of how Dynamic Binary Indexed Tree works.

If explained quickly:
we are representing the number in form of string and inerting them in tries.
every node stores the formed by the number formed that point.

The C++ implementation is coming soon.