树状数组插入操作，在x的位置加上k，那么需要往上爬到根节点为止，加上k
int tr[N]; int a[N];//原数组 1~n void add(int x,int k)//x的位置加上k { for(int i=x;i<=n;i=i+lowbit(i)) tr[i]+=k; }
树状数组查询操作：查询前缀和，进而查询区间和。
前缀和查询操作：查询一个点x的前缀和，就是对其以及其之前的点求和。在图中这棵树中，例如要求s[7]，可以从lowbit(7)可知它存储了一位数,而减去lowbit后的6存储着0110~0101两位数，
0100存储着100前的四个数，因此每次减去lowbit再相加返回结果即可算出前缀和。区间和因此也可以计算出来
int query(int x) { int sum=0; for(int i=x;i!=0;i-=lowbit(x)) { sum+=tr[i]; } return sum; }
4道题目:
在完成了分配任务之后，西部 314 来到了楼兰古城的西部。
相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹(∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。
西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 n 个点，经测量发现这 n 个点的水平位置和竖直位置是两两不同的。
西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关，因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn)，其中 y1∼yn 是 1 到 n 的一个排列。
西部 314 打算研究这幅壁画中包含着多少个图腾。
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi>yj,yj<yk，则称这三个点构成 V 图腾;
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi<yj,yj>yk，则称这三个点构成 ∧ 图腾;
西部 314 想知道，这 n 个点中两个部落图腾的数目。
因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。
输入格式
第一行一个数 n。
第二行是 n 个数，分别代表 y1，y2,…,yn。
输出格式
两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数。
数据范围
对于所有数据，n≤200000，且输出答案不会超过 int64。
y1∼yn 是 1 到 n 的一个排列。
输入样例：
5
1 5 3 2 4
输出样例：
3 4
来源于《算法进阶指南》
分析:观察到要严格v或者倒v型。
将点罗列在坐标系上，遍历每个点，计算以其为中心所得到的v型和倒v型数量
``如何计算？
得到其左侧的greater和less，右侧的greater和less，纯暴力复杂度为n^2
点的遍历不可优化，因此必须要优化greater和less的计算过程
注意到题目说y的范围是1~n的，不是整数范围的(也可以离散化做)
因此对于一个数来讲，只需要得到其左侧比它小的数的数量，就可以计算出左侧比它大的数数量为i-leftnum-1。
只要得到右侧比他小的数的数量，就可以得到右侧比他大的数的数量。
而左侧右侧可以互通，因此只需要算一次。
具体为：左侧小的数量设置为x，当前遍历的数的下标设置为i，数值设置为val,那么左侧大的数数量为i-1-x,右侧小的数数量为val-i-1,右侧大的数量为n-i-val+1+t
``如何计算左侧比它小的数的数量?
使用树状数组表示t[i]当前这个点在区间内比他小的数的数量。插入新的数x时，只需要计算t[x-1]的前缀和即可。
然后在a[i]的位置执行插入操作，当前位置+=1
接下来是代码
#include<bits/stdc++.h> #define dbg(x) cout<<#x<<" "<<x<<"n" #define ll long long using namespace std; const int N=2e5+10; ll y[N],t[N]; ll lle[N],rgr[N],lgr[N],rle[N]; ll n; ll lowbit(ll x) { return x&-x; } void add(ll x,ll k){ for(int i=x;i<=n;i=i+lowbit(i)) t[i]=t[i]+k; } ll query(ll x) { int res=0; for(int i=x;i>0;i=i-lowbit(i)) { res=res+t[i]; }//返回小于一个数字的所有数字。 return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;++i)cin>>y[i]; for(int i=1;i<=n;++i){ ll val=y[i]; ll t=query(val); lle[i]=t; lgr[i]=(i-1-t); rle[i]=(val-1-t); rgr[i]=(n-i-val+1+t);//n-i-(val-1-t)=n-i-val+1+t // dbg(i); // dbg(lle[i]); // dbg(lgr[i]); // dbg(rle[i]); // dbg(rgr[i]); add(val,1); } ll sum1=0,sum2=0; for(int i=1;i<=n;++i) { sum1+=lgr[i]*rgr[i]; sum2+=lle[i]*rle[i]; } cout<<sum1<<" "<<sum2; }
给定长度为 N 的数列 A，然后输入 M 行操作指令。
第一类指令形如 C l r d，表示把数列中第 l∼r 个数都加 d。
第二类指令形如 Q x，表示询问数列中第 x 个数的值。
对于每个询问，输出一个整数表示答案。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数 A[i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤105,
|d|≤10000,
|A[i]|≤109
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2
输出样例：
4
1
2
5
#include<bits/stdc++.h> using namespace std; #define mem(a) memset(a,0,sizeof(a)) #define dbg(x) cout<<#x<<" = "<<x<<endl #define fi(i,l,r) for(int i=l;i<r;i++) #define cd(a) scanf("%d",&a) #define pii pair<int,int> #define pb push_back #define pp pop_back #define pii pair<int,int> typedef long long ll; const int N=1e5+10; ll t[N];//tr表示当前子区间的差分和 ll a[N],d[N]; ll lowbit(ll x){return x&-x;}//差分存储,单点修改 ll n,m; void add(int x,int k){ for(int i=x;i<=n;i=i+lowbit(i)) t[i]+=k; } ll query(int x) { ll res=0; for(int i=x;i;i-=lowbit(i)) res+=t[i]; return res;//前缀和得到一个数 } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;++i){cin>>a[i];d[i]=a[i]-a[i-1];add(i, d[i]);} while(m--) { char op;cin>>op; if(op=='Q'){ int x;cin>>x; cout<<query(x)<<"n"; } else{ int l,r,d;cin>>l>>r>>d; add(l,d);add(r+1,-d); } } }
3.
原文链接: https://www.cnblogs.com/manamouse/p/17049291.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/311868
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
