Q:You are given an array of n elements. Now, there are 2 types of queries on the array. 1) Change the element at index i to some new element(say x). 2)Given l and r ,find the number of subarrays in range l to r having sum divisible by 3. The number of queries can be upto 1e5 and also size of the array can be upto 1e5.
This is not from some ongoing coding contest. I found this question on gfg from a company's interview experience. Link to that blog:- https://www.geeksforgeeks.org/nutanix-interview-experience-for-mts-intern-off-campus-2021/
You need to know for some segment, how many subarrays have $$$ sum \% 3 = 0 $$$. In order to do so, you can keep on each segment tree node, how many subarrays, preffixes and suffixes has that segment, such that their $$$ sum \% 3 = k $$$, for k = 0, 1, 2.
Yupp,I also got it now. But this would be pretty much implementation heavy right? Storing how many subarrays ,prefix, suffix, sum modulo 3 for that range for each 0,1 and 2
Yup, it's really annoying to code.
(I'm making the assumption that a[i] can't be zero)
Create a range sum segment tree on prefix sum array of given array A[] and in each node of the segment tree you will store the node value % 3, Now for a subarray [L, R] sum to be divisible by 3, sum of subarray A[0, L-1] % 3 should be equal to sum of subarray A[0, R] % 3,
So you can store the count of 0, 1 and 2's in each node and based on that you can count the total number of possible subarrays with sum % 3 == 0.
You should be able to handle the updates part yourself now I think
Feel free to correct me in case I missed something :)
If a[i]=0, how does that make things different. Btw for updates, u need a lazy segtree to count and update the prefix sums right?
On second thought A[i] == 0 shouldn't affect the solution, and yah you need lazy for range updates
You only have point updates in this problem.