优点修改和查询树状数组的前缀和复杂度为Ologn注意点树状数组对下标有要求必须从1开始1-base1.求数组前缀和将原数组数组放入树状数组直接求sum即可2.求数组某个元素的值将原数组的差分数组放入树状数组求sum3.求逆序对知识点离散化目的节约内存让下表更清晰去重节约时间复杂度实现代码sort(t1,tn1); cntunique(t1,tn1)-t-1;将离散化后的数组按顺序插入树状数组求前缀和n-前缀和a[i].模板#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define pb push_back #define dbg(x) std::cout#x:x typedef long long ll; typedef pairint,int PII; const int N500005; ll n,m; ll a[N]; ll lowbit(ll x) { return (x(-x)); } void update(ll x,ll v){ while(xn){ a[x]v; xlowbit(x); } } ll sum(ll x){ ll res0; while(x0){ resa[x]; x-lowbit(x); } return res; } void solve() { cinnm; ll wn; ll tp; while(w--){ cintp; update(n-w,tp); } ll a1,a2,a3; while(m--){ cina1a2a3; if(a11){ update(a2,a3); } if(a12){ if(a21) coutsum(a3)-sum(a2-1)endl; else coutsum(a3)endl; } } } int main() { IOS int T1;//cinT; while(T--) solve(); return 0; }#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define pb push_back #define dbg(x) std::cout#x:x typedef long long ll; typedef pairint,int PII; const int N500005; int n,m; int a[N],b[N]; int lowbit(int x) { return (x(-x)); } void update(int x,ll v){ while(xn){ a[x]v; xlowbit(x); } } ll sum(int x){ ll res0; while(x0){ resa[x]; x-lowbit(x); } return res; } void solve() { cinnm; int wn; ll tp; for(int i1;in;i){ cinb[i]; update(i,b[i]-b[i-1]); } ll a1,a2,a3,a4; while(m--){ cina1; if(a11){ cina2a3a4; update(a2,a4); update(a31,-a4); } if(a12){ cina2; coutsum(a2)endl; } } } int main() { IOS int T1;//cinT; while(T--) solve(); return 0; }例题题都不难放了几个典型的洛谷——逆序对#include bits/stdc.h using namespace std; typedef long long ll; const int N5e55; int n,cnt; ll a[N],b[N],t[N],ans; int lowbit(int x){ return x(-x); } void update(int x){ while(xn){ a[x]; xlowbit(x); } } ll sum(int x){ ll res0; while(x0){ resa[x]; x-lowbit(x); } return res; } void solve() { cinn; for(int i1;in;i){ cinb[i]; t[i]b[i]; } sort(t1,tn1); cntunique(t1,tn1)-t-1; for(int i1;in;i){ //按原顺序插入 b[i]lower_bound(t1,tcnt1,b[i])-t;//更新离散化后的序号 update(b[i]); //比当前元素大的当前元素个数-小于等于它的元素个数 anssum(n)-sum(b[i]); } printf(%lld\n,ans); } int main() { solve(); return 0; }数星星可以不用逆序对#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define pb push_back #define dbg(x) std::cout#x:x typedef long long ll; typedef pairint,int PII; const int N32005; struct z{ int x,y; }; int n,m,MAX0; int a[N],ans[N]; z p[N]; int lowbit(int x) { return (x(-x)); } void update(int x,int v){ while(xN){ a[x]v; xlowbit(x); } } ll sum(int x){ ll res0; while(x0){ resa[x]; x-lowbit(x); } return res; } void solve() { scanf(%d,n); int x,y; for(int i1;in;i){ scanf(%d %d,p[i].x,p[i].y); } for(int i1;in;i){ update(p[i].x1,1); int vsum(p[i].x1); ans[v-1]; } for(int i0;in;i){ coutans[i]endl; } } int main() { int T1;//cinT; while(T--) solve(); return 0; }逆序对写法和上个题基本一样按顺序求x的逆序对就好了不写了其实这个题有别的做法我把update里的加改成了异或#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define pb push_back #define dbg(x) std::cout#x:x typedef long long ll; typedef pairint,int PII; const int N5000005; int n,m; int a[N],b[N]; int lowbit(int x) { return (x(-x)); } void update(int x,int v){ while(xn){ a[x]^v; xlowbit(x); } } ll sum(int x){ ll res0; while(x0){ res^a[x]; x-lowbit(x); } return res; } void solve() { cinnm; ll a1,a2,a3; while(m--){ scanf(%lld,a1); if(a11){ scanf(%lld %lld,a2,a3); update(a2,1); update(a31,1); } if(a12){ scanf(%lld,a2); coutsum(a2)endl; } } } int main() { int T1;//cinT; while(T--) solve(); return 0; }