Appropriate data structure for adding +1/-1 to ranges and finding the last index with value 0

Правка en1, от color_me_red, 2017-07-19 17:36:40

I have an array a of values +1 and -1 in random order, and a separate array s which is initialised with 0 in every position. I run through the array from left to right. At every index i, I add the value of a[i] across s[0], s[1], ... , s[i-1], s[i]. And at every index i, after doing the previous operation, I want to return the rightmost index in the range [0, i] with value 0. If no such index exists, I'll return some invalid number like -1.

The adding operation can be done using a Fenwick tree. But I have no clue to find the rightmost index in logarithmic complexity. I'm trying to do the entire process in O(n) or O(nlogn) complexity. Any idea would be much appreciated, thanks!

Теги #data structure, array

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский color_me_red 2017-07-19 17:36:40 799 Initial revision (published)