Find count of subarrays having sum in a given range in less than O(n^2).

→ Обратите внимание

До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя code_fille

Find count of subarrays having sum in a given range in less than O(n^2).

Автор code_fille, история, 9 лет назад, По-английски

Given an array of integers and a range find the count of subarrays whose sum lies in the given range. Do so in less than O(n^2) complexity.

subarray

code_fille
9 лет назад
22

Комментарии (17)

Показать архивные | Написать комментарий?

RedNextCentury

9 лет назад, # |

← Rev. 6 →

+10

let us call the range [ l, r ] build the prefix sum array for the given array, let us call it B (B[0]=0 for empty prefix)

now
B[i] - B[j] where 0 ≤ j < i
gives all the sums of subarrays that end in i^th element

So, in order for the sum of subarray [ j + 1...i ] to be between l and r the following should be true:

l ≤ B[i] - B[j] ≤ r
=>
l - B[i] ≤ - B[j] ≤ r - B[i]
=>
B[i] - l ≥ B[j] ≥ B[i] - r

so for each B[i], we should find the number of B[j] s that are in the previous range and j < i, which is done in a segment tree

total complexity: O(nlogn)

NOTE If the values are all positive you can use binary search for O(nlogn)

→ Ответить

code_fille

9 лет назад, # ^ |

How could segment tree be used to find the possible values of j?

→ Ответить

RedNextCentury

9 лет назад, # ^ |

← Rev. 3 →

Array C , C[i] is the number of B[j]'s which are equal to i
You need a segment tree to perform 2 types of queries:
1) add 1 to C[x]
2) get the sum of C[x] : s<=x<=e

So for each B[i] you query for the sum of C[x] between B[i]-r and B[i]-l Then you add 1 to C[B[i]]

→ Ответить

Dazzler

6 лет назад, # ^ |

B[i] can be negative ..how it is possible to store in array?

→ Ответить

Vasiljko

6 лет назад, # ^ |

Then compress the values

→ Ответить

Dazzler

6 лет назад, # ^ |

I was trying to solve this question. I tried to compress the values. But it is giving WA. Here is the code. Please help me.

→ Ответить

Vasiljko

6 лет назад, # ^ |

You will have at most N+2 different values (Including L and R), compress them.

→ Ответить

Dazzler

6 лет назад, # ^ |

Can you please have a glance at my code?

→ Ответить

Dazzler

6 лет назад, # ^ |

For each B[i], I have to put B[i]-l and B[i]-r. I have to compress n*2*n values.

→ Ответить

zephyr_23

6 лет назад, # ^ |

Were you able to solve that question ? If yes, can you please share the code? I am also getting W.A.

→ Ответить

Dazzler

6 лет назад, # ^ |

Yes, I solved it Here is the code

→ Ответить

SashaMN

9 лет назад, # ^ |

← Rev. 2 →

If the values are all positive you can solve in O(N) using only 3 pointers.

Note: You can also solve in O(NlogN) without segment tree, just using divide-and-conquer idea.

→ Ответить

code_fille

9 лет назад, # ^ |

Could you elaborate how divide and conquer could be used?

→ Ответить

SashaMN

9 лет назад, # ^ |

← Rev. 3 →

B — partial sum, B[0] = 0.

$\text{[math]}$

Now we are going to split our verctor a into 2 parts with size N / 2 each.

2 cases are possible:

1) l, r < N / 2 or l, r > N / 2: We can find the answer recursively for the left part and for the right part.

2) l < N / 2 and r > N / 2: We can find the answer in O(N) using 3 pointers but only if the left part sorted and the right part sorted too. But you can maintain these parts sorted by using merge sort algorithm.

The algorithm is very similar to the algorithm for counting inversions in O(NlogN) time. You can find the explanation on coursera: link

→ Ответить