Java O(logN) for each query with bit manipulation and binary search
Observation: If there is a majority element, then each bit of its binary number must also be majority. For example, [3,3,4,7,3]. In binary, it\'s \n[011,\n011, 
Observation: If there is a majority element, then each bit of its binary number must also be majority. For example, [3,3,4,7,3]. In binary, it\'s \n[**011**,\n**011**,  \n100, \n1**11**, \n**011**]. \nThen collect the majority of each bit, we have 011, which is the answer 3.\n\nWe can maintain an array presum[i][j], denoting the total number of 1\'s on bit j for the first i numbers. This can be done in initialization. With this, when query, we can get all majority bits in O(1) time (since there are at most 15 bits). If there exists a bit for which we cannot find a majority, return -1. Otherwise, we get a candidate.\n\nHowever, be careful here. This candidate may not be the final answer. For example, [1,2,3]. In binary, it\'s [01, 10, 11]. Bit-majority is 11, candidate=3. But clearly, we shouldn\'t have a majority here. In order to get rid of the false positive, we need to know exactly how many times this candidate appears in the subarray. This can be achieved in O(logN)-time binary search if we have a list of occurrences of this number.\n\nOverall, O(logN) for each query, and O(N) for initialization, where N is the size of the given array.\n\nAny comment or counter-example is welcome.\n```\nclass MajorityChecker {\n    \n    private final int digits=15;\n    private int[][]presum;\n    private ArrayList<Integer>[]pos;\n    \n    public MajorityChecker(int[] arr) {\n        int len=arr.length;\n        presum=new int[len+1][digits];\n        pos=new ArrayList[20001];\n        \n        for(int i=0;i<len;i++){\n            int n=arr[i];\n            if(pos[n]==null)pos[n]=new ArrayList();\n            pos[n].add(i);\n            \n            for(int j=0;j<digits;j++){\n                presum[i+1][j]=presum[i][j]+(n&1);\n                n>>=1;\n            }\n        }\n    }\n    \n    public int query(int left, int right, int threshold) {\n        int ans=0;\n        for(int i=digits-1;i>=0;i--){\n            int cnt=presum[right+1][i]-presum[left][i];\n            int b=1;\n            if(cnt>=threshold)b=1;\n            else if(right-left+1-cnt>=threshold)b=0;\n            else return -1;\n            ans=(ans<<1)+b;\n        }\n        \n        // check\n        ArrayList<Integer>list=pos[ans];\n        if(list==null)return -1;\n        int L=floor(list,left-1);\n        int R=floor(list,right);\n        if(R-L>=threshold)return ans;\n        return -1;\n    }\n    \n    private int floor(ArrayList<Integer>list,int n){\n        int left=0, right=list.size()-1, mid;\n        while(left<=right){\n            mid=left+(right-left)/2;\n            int index=list.get(mid);\n            if(index==n)return mid;\n            else if(index<n)left=mid+1;\n            else right=mid-1;\n        }\n        return right;\n    }\n    \n}\n```\n
['Binary Search', 'Bit Manipulation', 'Java']