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

Revision en1, by 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!

Tags #data structure, array

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English color_me_red 2017-07-19 17:36:40 799 Initial revision (published)