树状数组
主要用途
tips：绝对不能使用0作为下标(与二进制的性质有关)
倒着数到最后一个1然后把前面都变成0(其实就是去补的取反加1)
构造数组
单点修改
区间查询
将几个部分加起来就是一段完整的区间和。
那我们要如何对于找到完全无缝衔接的t呢，将最大的那个数组减去对应的lowbit就可以得到我们所要找的那个与其无缝相邻的较小的数组。
区间修改
原本的单点修改是利用树状数组来维护前缀和，区间修改则是利用树状数组来维护差分数组。
将其分成两个部门一个为t1一个为t2某种角度来看定点修改是区间修改的特殊情况。
【模板】树状数组（单点修改）
题目描述
给定一个大小为nn个数组aa，qq次操作。
每次操作分为下面两种：
"1 k v"：给a_k加上v。
"2 l r"：查询区间[l, r][l,r]的和。
对于每次22操作，输出结果。
输入格式
第一行两个整数n,q。
第二行n个整数表示数组a。
接下来q行，每行一个操作。
输出格式
对于每次22操作，在一行内输出结果。
样例输入1
5 4
1 2 3 4 5
1 1 1
2 1 2
1 4 2
2 3 4样例输出1
4
9#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+9;
int a[N],t[N];
stack<int> stk;
vector<int> X;
int n,q;
int getidx(int x){
//通过lower_bound 的二分查找第一个大于等于的的元素的迭代器
//返回值范围为[1,X.size()]
return lower_bound(X.begin(),X.end(),x)-X.begin()+1;
}
int lowbit(int x){
return x&-x;
}
void update(int k,int x){
for(int i =k;i<=n;i+=lowbit(i))t[i]+=x;
}
int getsum(int k){
int res = 0;
for(int i = k;i > 0;i-=lowbit(i))res+=t[i];
return res;
}
void solve(){
cin>>n>>q;
for(int i = 1;i<=n;i++) cin>>a[i];
// 先默认树状数组为全0，然后再进行修改
for(int i = 1;i<=n;++i)update(i,a[i]);
while(q--){
int op;cin>>op;
if(op == 1){
int l,r;
cin>>l>>r;
update(l,r);
}
else{
int l,r;cin>>l>>r;
cout<<getsum(r)-getsum(l-1)<<'\n';
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
while(_--)solve();
return 0;
}[P41] 树状数组（区间修改）
题目描述
给定一个大小为n个数组a，q次操作。
每次操作分为下面两种：
"1 l, r v"：给区间[l, r][l,r]中的数组加上v。
"2 l r"：查询区间[l, r][l,r]中数字的和。
对于每次2操作，输出结果。
输入格式
第一行两个整数n,q。
第二行n个整数表示数组a。
接下来q行，每行一个操作。
输出格式
对于每次2操作，在一行内输出结果。
样例输入1
5 4
1 2 3 4 5
1 1 3 1
2 1 2
1 4 5 2
2 3 4样例输出1
5
10#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+9;
int a[N],td[N],tdi[N];
stack<int> stk;
vector<int> X;
int n,q;
int lowbit(int x){
return x&-x;
}
void update(int k,int x){
for(int i =k;i<=n;i+=lowbit(i))
{
td[i]+=x;
tdi[i]+=k*x;
}
}
int getsum(int k){
int res = 0;
for(int i = k;i>0;i-=lowbit(i))
res+=(k+1)*td[i]-tdi[i];
return res;
}
void solve(){
cin>>n>>q;
for(int i = 1;i<=n;i++) cin>>a[i];
// 先默认树状数组为全0，然后再进行修改
for(int i = 1;i<=n;++i)
{
update(i,a[i]);
update(i+1,-a[i]);
}
while(q--){
int op;cin>>op;
if(op == 1){
int l,r,v;
cin>>l>>r>>v;
update(l,v);
update(r+1,-v);
}
else{
int l,r;cin>>l>>r;
cout<<getsum(r)-getsum(l-1)<<'\n';
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
while(_--)solve();
return 0;
}洛谷P1908） 逆序对
题目描述
猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。
输入格式
第一行，一个数n，表示序列中有n个数。
第二行n个数，表示给定的序列。序列中每个数字不超过10^9
输出格式
给定序列中逆序对的数目。
当然逆序对也可以用归并排序的方法求，但树状数组的空间复杂度更低。其实我们与其说在用树状数组求逆序对，不如说是在求非严格顺序对（顺序对和相等对），然后间接算出逆序对的数量。我们是怎么算出非严格顺序对的个数的呢？
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+9;
int a[N],t[N],tdi[N];
stack<int> stk;
vector<int> X;
int n,q;
int bin(int x){
return lower_bound(X.begin(),X.end(),x)-X.begin()+1;
}
int lowbit(int x){
return x&-x;
}
void update(int k,int x){
for (int i = k; i <= X.size(); i+= lowbit(i)) {
t[i]+=x;
}
}
int getsum(int k){
int sum = 0;
for (int i = k; i >0 ; i-= lowbit(i)) {
sum+=t[i];
}
return sum;
}
void solve(){
cin>>n;
for(int i = 1;i<=n;i++)cin>>a[i];
for(int i = 1;i<=n;i++){
X.push_back(a[i]);
}
//排序去重
sort(X.begin(),X.end());
X.erase(unique(X.begin(),X.end()),X.end());
int ans = 0;
for(int i = 1;i<=n;i++){
ans+= getsum(X.size())- getsum(bin(a[i]));
update(bin(a[i]),1);
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
while(_--)solve();
return 0;
}这道题的本质其实就是求一个数读入前有几个数是大于他的。
例如，我们要求5 4 1 3 2的逆序对。用ans记录非严格顺序对的数量。
我们按顺序去填充树状数组，第一个数字是5，这时没有数比5小，所以ans保持为0。我们把tree[5]填为1。
下一个数字是1，这时也没有数比1小，ans仍为0。我们把tree[1]填为1。
下一个数字是3，这时query(3)为1，有一个数比3小了，ans变为1。然后再填tree[3]。
下一个数字是2，这时query(2)为1，说明前面有一个数比2小，ans再加1变为2。然后填tree[2]。
最后一个数字是4，query(4)为3，说明前面有3个数比4小，ans加3变为5。所以非严格顺序对的总数就是5。那么逆序对共有 C52−5=5 个。
每进行上述过程一次，我们就要进行一次求和，相当于将求从当前位置到数组末尾的的前缀和。
