Prefix sums, Bitwise AND
Given an array, find whether Bitwise AND of a range A[L], A[L+1], ... A[R] is even or odd.
The main observation here is that if there is atleast one even number in the required range, answer will be even (Think why?).
To solve the reduced problem of finding whether there is an even number in the range, make a prefix array which will tell number of even numbers upto index i. Then for each query calculate pre[R] - pre[L-1]. If the value is greater than 0 then the answer is “EVEN” else the answer is “ODD”.