题目描述：
给出整数序列，每次修改其中一个数的值，或给出$x,y$询问 $\sum_{i=1}^{n}(a_i+x)\&y$。
解题思路：
看到位运算，要想到按位做。因为$x\&2^i$的结果随$x$是循环的，有$2^i$个$0$， $2^i$个$2^i$轮流出现。所以我们记录$x\%2^{i+1}$的值，这样$x$和$2^i$操作后有值时，仅当$x\%2^{i+1}$的结果在$[2^i,2^{i+1})$。而因为询问时会加上一个数，所以我们要把它减掉，如果减掉后区间有负怎么办。注意到前面说是循环的，所以把负的那段补到后面就好了。
代码：
1 #include2 #include 3 #include 4 #define i64 long long 5 using namespace std; 6 7 const int N = 1e5 + 10; 8 int n, q, a[N], Sum[21][1 << 21], pow[21]; 9 i64 ans;10 11 int lowbit(int x) { return x & -x;}12 13 void add(int x, int p, int v) {14 p ++;15 while (p <= pow[x + 1] + 1) Sum[x][p] += v, p += lowbit(p); 16 }17 18 int sum(int x, int p) {19 int r = 0;20 p ++;21 while (p) r += Sum[x][p], p -= lowbit(p);22 return r;23 }24 25 int main() {26 pow[0] = 1;27 for (int i = 1; i <= 20; i ++) pow[i] = pow[i - 1] * 2;28 scanf("%d %d", &n, &q);29 for (int i = 1; i <= n; i ++) {30 scanf("%d", &a[i]);31 for (int j = 1; j <= 20; j ++) add(j - 1, a[i] % pow[j], 1);32 }33 while (q --) {34 int opt, x, y;35 scanf("%d %d %d", &opt, &x, &y);36 if (opt == 1) {37 for (int i = 1; i <= 20; i ++) add(i - 1, a[x] % pow[i], -1);38 a[x] = y;39 for (int i = 1; i <= 20; i ++) add(i - 1, a[x] % pow[i], 1);40 }41 if (opt == 2) {42 ans = 0;43 for (int i = 1; i <= 20; i ++) if (y & pow[i - 1]) {44 int l = pow[i - 1], r = pow[i] - 1, t;45 l = (l - x - 1 + pow[20]) % pow[i];46 r = (r - x + pow[20]) % pow[i];47 if (l <= r) t = sum(i - 1, r) - sum(i - 1, l);48 else t = sum(i - 1, r) + sum(i - 1, pow[i]) - sum(i - 1, l);49 ans += 1ll * t * pow[i - 1];50 }51 printf("%lld\n", ans);52 }53 }54 return 0;55 }