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...
Dynamic Segment Trees Dynamic Segment Trees. Here we go. Problem Statement You are given the value of N (size of the array initialized to 0) and Q queries to process online 1 P V Put value V at position P . 2 L R Output the sum of values from L to R . Constraints: 1<=N<=10^18 Q<=10^5 1<=L<=R<=N Queries are online L=(previousAnswer+L)%N+1; R=(previousAnswer+R)%N+1; Examples: Input : 5 5 1 2 3 1 1 4 1 3 5 1 4 7 2 3 4 Output : 12 Input : 3 2 1 1 1 1 2 2 1 3 3 Output : 0 Why we need Dynamic Segment trees. let’s dive deep into it. Let’s solve the problem bit by bit. At first, consider low constraints and offline queries. This can be done simply by using a Segment Tree or a Fenwick/binary Indexed Tree. A standard problem for segment trees. but the problem occurs when you get high constraints. Like when 1<=N<=10^18. this much size can't be allocated as an ar...