P3374 【模板】树状数组 1
树状数组的初始长相其实跟 \(st\) 有点像，都是像二进制一样拼接而来，那么原始树状数组中数据其实就是被这一层包含的下一层的数据之和。那么我们借鉴一下老师的图。
然后我们其实可以去掉一些空间，因为我们可以发现所有偶数位置上的数据可以通过奇数位求出来。那么偶数位就是可有可无的。简称无用区间。
那么我们定义树状数组 \(c_i\) 表示以 \(i\) 为结尾，长度为 \(2^?\) 的取件答案。是的，就是 ? 号次方。我们可以推导一下。当假设 \(a_i\) 为 原数组，\(c_i\) 为树状数组。
c[1] = a[1];
c[2] = a[1] + a[2];
c[1] = a[3];
c[2] = a[1] + a[2] + a[3] + a[4];
那么我们可知 \(c_i\) 代表的区间长度为 \(i , i + 2^i - 1\)。同时根据以上数据可知每次隔了一个后就立马进行区间合并。然后，我们应该怎么求区间答案呢？
首先我们先了解一下只保留奇数位置的数据时怎么求偶数位，首先当要的只再奇数位是就不用管，直接加。否则我们现在的答案减去奇数位就可以得出偶数位。
那么，我们就可以先加上区间 \([x - lowbit(x) + 1 , x]\) 的和，然后我们进行二进制拆分，知道 \(x <= 0\) 即可。
只与修改的话，我们可以发现如果修改一个数那么其实只有与这个数有关的发生变化。比如你加上 \(k\) 那么你的上司，你上司的上司都加上，一直到老板都加上 \(k\)。那么就一个往上找上司，让后修改答案。
那么其实 \(c_i\) 被 \(c_{i + lowbit(i)}\) 包含的话其实就可以直接建边的。那么此题可解。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int c[1000005];
int a[1000005];
int n,m;
int lowbit(int x){return (x & (-x));
}
int query(int x){int ans = 0;while(x > 0){ans += c[x];x -= lowbit(x);}return ans;
}
void modify(int idx,int val,int k){while(idx <= k){c[idx] += val;idx += lowbit(idx);}
}
void build(){for(int i = 1 ; i <= n ; i ++){modify(i , a[i] , n);}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n >> m;for(int i = 1 ; i <= n ; i ++){cin >> a[i];}build();while(m --){int op,l,r;cin >> op >> l >> r;if(op == 1){modify(l , r , n);}else{cout << query(r) - query(l - 1) << "\n"; }}return 0;
}P3368 【模板】树状数组 2
这一次我们的修改时区间修改，那么什么算法能解决区间修改呢？差分就是一个好帮手，那么我们就可以对数组做差分。
我们知道修改时差分时左端点加上 \(x\) 右端点加一减去 \(x\) 那么我们的修改就从原来的修改一个点改成做差分后的数组修改左端点和右端点加一即可。
其余不变
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int c[1000005];
int b[1000005];
int a[1000005];
int n,m;
int lowbit(int x){return (x & (-x));
}
int query(int x){int ans = 0;while(x > 0){ans += c[x];x -= lowbit(x);}return ans;
}
void modify(int idx,int val,int k){while(idx <= k){c[idx] += val;idx += lowbit(idx);}
}
void build(){for(int i = 1 ; i <= n ; i ++){modify(i , b[i] , n);}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n >> m; for(int i = 1 ; i <= n ; i ++){cin >> a[i];b[i] = a[i] - a[i - 1];}build();while(m --){int op;int x,y,k;cin >> op;if(op == 1){cin >> x >> y >> k;modify(x , k , n);modify(y + 1, -k , n);}else{cin >> x;cout << query(x) << "\n";}}return 0;
}