algorithm - how to read all 1's in an Array of 1's and 0's spread-ed all over the array randomly -

i have array 1 , 0 spread on array randomly.

int arr[n] = {1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,1....................n} 

now want retrive 1's in array fast possible, condition should not loose exact position(based on index) of array , sorting option not valid. option left linear searching ie o(n) , there better this.

the main problem behind linear scan , need run scan x times. feel need have kind of other datastructure maintains list once first linear scan happens, need not run linear scan again , again.

let me clear final expectations- 

i need find number of 1's in range of array , precisely need find numbers of 1's in array within range of 40-100. can random range , need find counts of 1 within range. can't sum , need iterate on array on , on again because of different range requirements

i'm surprised considered sorting faster alternative linear search.

if don't know ones occur, there no better way linear searching. perhaps if used bits or char datatypes optimizations, depends on how want use this.

the best optimization on overcome branch prediction. because each value 0 or one, can use advance index of array used store one-indices.

simple approach:

int end = 0; int indices[n];  for( int = 0; < n; i++ ) {     if( arr[i] ) indices[end++] = i;  // slow due branch prediction } 

without branching:

int end = 0; int indices[n];  for( int = 0; < n; i++ ) {     indices[end] = i;     end += arr[i]; } 

---

[edit] tested above, , found version without branching 3 times faster (4.36s versus 11.88s 20 repeats on randomly populated 100-million element array).

coming here post results, see have updated requirements. want easy dynamic programming approach...

all create new array 1 element larger, stores number of ones beginning of array (but not including) current index.

arr   :   1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 count : 0 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 5 6 6 6 6 7 

(i've offset arr above lines better)

now can compute number of 1s in range in o(1) time. compute number of 1s between index a , b, do:

int num = count[b+1] - count[a]; 

obviously can still use non-branch-prediction version generate counts initially. should give pretty speedup on naive approach of summing every query:

int *count = new int[n+1]; int total = 0;  count[0] = 0;  for( int = 0; < n; i++ ) {     total += arr[i];     count[i+1] = total; }   // compute ranged sum: int range_sum( int *count, int a, int b ) {     if( b < ) return range_sum(b,a);     return count[b+1] - count[a]; }