一,模板
树状数组
1264. 动态求连续区间和
#include<iostream>
#define lowbit(x) (x&-x)
using namespace std;
typedef long long LL;
const int N=100010;
int n,m;
LL tr[N];
void add(int x,int k)
{
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=k;
}
LL sum(int x)
{
LL res=0;
for(int i=x;i;i-=lowbit(i)) res+=tr[i];
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
int x;
scanf("%d",&x);
add(i,x);
}
while(m--)
{
int k,a,b;
scanf("%d%d%d",&k,&a,&b);
if(k) add(a,b);
else printf("%lld\n",sum(b)-sum(a-1));
}
return 0;
}
ST表
1270. 数列区间最大值
#include<iostream>
#include<cmath>
using namespace std;
const int N=100010,M=17;
int n,m;
int w[N];
int f[N][M];
void init_st()
{
for(int j=0;j<M;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
if(!j) f[i][j]=w[i];
else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int query(int l,int r)
{
int k=log(r-l+1)/log(2);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&w[i]);
init_st();
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",query(a,b));
}
return 0;
}
线段树
243. 一个简单的整数问题2
#include<iostream>
using namespace std;
typedef long long LL;
const int N=100010;
int n,m;
struct Node{
int l,r;
LL sum,add;
}tr[N*4];
LL w[N];
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)
{
if(tr[u].add)
{
auto &U=tr[u],&L=tr[u<<1],&R=tr[u<<1|1];
L.sum+=(LL)(L.r-L.l+1)*U.add,R.sum+=(LL)(R.r-R.l+1)*U.add;
L.add+=U.add,R.add+=U.add,U.add=0;
}
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u]={l,r,w[l],0};
return;
}
tr[u]={l,r};
int mid=(l+r)/2;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int d)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
tr[u].add+=d;
return;
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)/2;
if(l<=mid) modify(u<<1,l,r,d);
if(mid<r) modify(u<<1|1,l,r,d);
pushup(u);
}
LL query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)
return tr[u].sum;
pushdown(u);
int mid=(tr[u].l+tr[u].r)/2;
LL res=0;
if(l<=mid) res+=query(u<<1,l,r);
if(mid<r) res+=query(u<<1|1,l,r);
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",w+i);
build(1,1,n);
while(m--)
{
char op[2];
int l,r,d;
scanf("%s%d%d",op,&l,&r);
if(*op=='C')
{
scanf("%d",&d);
modify(1,l,r,d);
}
else printf("%lld\n",query(1,l,r));
}
return 0;
}
二,例题部分
题1 1265. 数星星
#include<iostream>
#define lowbit(x) (x&-x)
using namespace std;
const int N=32010;
int n;
int tr[N],cnt[N];
void add(int x,int k)
{
for(int i=x;i<N;i+=lowbit(i)) tr[i]+=k;
}
int sum(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=tr[i];
return res;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
x++;
cnt[sum(x)]++;
add(x,1);
}
for(int i=0;i<n;++i) printf("%d\n",cnt[i]);
return 0;
}
题2 1215. 小朋友排队
#include<iostream>
#include<cstring>
#define lowbit(x) (x&-x)
using namespace std;
typedef long long LL;
const int N=1000010;
int n;
int h[N],tr[N];
int cnt[N];
void add(int x,int k)
{
for(int i=x;i<N;i+=lowbit(i)) tr[i]+=k;
}
int sum(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=tr[i];
return res;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%d",&h[i]),++h[i];
for(int i=0;i<n;++i)
{
cnt[i]+=sum(N-1)-sum(h[i]);
add(h[i],1);
}
memset(tr,0,sizeof tr);
for(int i=n-1;i>=0;--i)
{
cnt[i]+=sum(h[i]-1);
add(h[i],1);
}
LL res=0;
for(int i=0;i<n;++i) res+=(LL)cnt[i]*(cnt[i]+1)/2;
printf("%lld",res);
return 0;
}