## Editorial for RGPC '18 P4 - Higgs

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: RuAr

Since we have to check which ticks are prime, we can use the Sieve of Eratosthenes to generate a list of primes. We then have to perform interwoven updates and queries, meaning that both operations must be efficient. Using traditional data structures, we can only achieve imbalanced and operations (with prefix sum/difference arrays), or and operations (with Binary Indexed Trees or BITs). We thus have to use a range update and range query binary indexed tree that would enable for both operation types.

We notice that, given a single range update of by , and then a query to the sum of elements in the range , there are 3 possibilities for the value of the sum:

We see that we can express this sum in the form , where is the value in the array at index after update, and is a "fix" value that we subtract in order to correct the sum. The value of varies depending on (draw it out for better understanding):

Showing that this idea generalizes to multiple updates and queries is left as an exercise for the reader. With this mathematical formulation, we can use 2 BITs to implement this algorithm: one to store the accumulated values (which we maintain like a normal range update point query BIT), and one to store the accumulated corrections.

Or, you know, use a segment tree with lazy propagation, but the BIT solution is less clunky.

Time complexity: