### THE_THUNDERSTORM_BEGINS's blog

By THE_THUNDERSTORM_BEGINS, history, 3 months ago,

in this blog i wanna demonstrate a stratigy that i came up with recently

Its usefull to calculate number of arrays with a sum of K in O(nlog(n)) complexity

If we had an array a with n elements

We loop through the indices At each index we consider all subarrays  ending with the current element

As we are interested in subarray sum We make a map to calculate how many times does a sum occer

at each index do the following

-add the value a[i] to all subarrays in the map

The thing is The second one will take up to O(n) How to solve this

Simply we use the WINK WINK ;) stratigy Like this Add a[i] to all past sums WINK WINK ;)

Make a variable sh (initially 0) That represents the added value to all the subarrays imagine us having  sums  1 2 3 If we add to them 2

and if we wanna find how many times does 5 occer we search for 3 (5-2)

In particular add a[i] to sh

And from now on if we wanna find how many times does the sum S occur

We search for map[k-sh]

so if we wanna count how many times does a sum K occur We add map[k-sh]  at each index

A simple implementation is like this

int main()
{
map<int, int> mp;
int n, sh = 0, res = 0, k;
cin >> n >> k;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
{
mp[-sh]++;
sh += a[i];
res += mp[k-sh];
}
cout << res;
}


this takes up to O(nlog(n)) time because of map complexity

Here are some problems that we can use the WINK WINK ;) stratigy in:

Good subarrays : https://codeforces.com/problemset/problem/1398/Cv

Subarray with Maximum Product?: https://codeforces.com/problemset/problem/1398/C

Singhal and Multiplication: https://codeforces.com/gym/102767

if you have usefull problems please comment them so i can add them to this blog. Goodbye and have fun coding ;)

 » 3 months ago, # |   0 Auto comment: topic has been updated by THE_THUNDERSTORM_BEGINS (previous revision, new revision, compare).
 » 3 months ago, # |   0 Auto comment: topic has been updated by THE_THUNDERSTORM_BEGINS (previous revision, new revision, compare).
 » 3 months ago, # |   +22 how did you get to Expert without knowing this before...
•  » » 3 months ago, # ^ |   +4 Training and solving harder problems is all i needed. a lot of algorithms help like segmenttree or binary search I had a problem with subarrays and felt good after discovering this Posted so that it helps other to understand this .
•  » » 3 months ago, # ^ | ← Rev. 4 →   +17 because he has a mind (pure IQ) no knowledge