Today is my birthday, on this occasion, let me share something I have learned over the last few weeks. I did a bit of problem solving these days. Learned some thing new
Problem statement: Given an array, you have Q queries, each query gives you l and r. You want smartly compute a[l] & a[l + 1] & .. & a[r].
Called init[i][j] = 1 if the j-th bit of i-th number is turned on. For every column of init. Compute the prefix sum of this column. Now for each query l and r. Consider the i-th bit, the prefix sum size n of column i as b, if the there are r - l + 1 number of 1’s between l and r. Add 2 ^ i to the answer.
Problem statement: Given an array, you have Q queries, each query gives you a number c. You want to smartly compute a[0] & c + a[1] & c + .. + a[n - 1] & c
Call count[i] as the number of turned on bit of every number in a. For every turned on i-th bit in a. Add count[i] * 2 ^ i to the answer.
I finally now understand and can implement basic segment tree problems.