java 实现线段树_线段树 学习笔记

板子题

1474: 【区间维护】小A的课堂2

时间限制: 1 Sec 内存限制: 128 MB

题目描述

小A同学总是在FLY的课上时处于神游状态亦或是休眠状态，所以小A对FLY到底讲了什么是一无所知。然而，FLY总是打断小A的休眠状态，并问他问题。作为小A的小伙伴，你当然不希望小A同学翻车(不然下一个回答问题的人就是你啦)。所以你需要编写个程序帮助小A求出每个知识点到底讲的难度有多深。已知FLY在课上一共扯到了1到N个知识点，每个知识点都有一个初始难度值，FLY会进行M个动作(每个动作包括讲课和提问)，其中，

动作1：讲课，该动作会使得一段连续的知识点的难度值上升P(P有可能为负数)

动作2：提问，该动作需要小A回答某一段连续知识点的难度值之和

输入

第一行包括两个数字$N$，$M$，表示知识点个数和FLY的动作次数

第二行包括$N$个数字，分别表示$1$到$N$个知识点的难度值

接下来$M$行，每行代表操作，若第$1$个数字为$1$，则代表该动作为讲课，接下来是三个变量$l，r，P$,代表$l$到$r$区间的知识点难度值上升$P$；若第$1$个数字为$2$，则代表该动作为提问，接下来是$2$个变量$l,r$，代表询问$l,r$之间的难度值和。

输出

每次小A的回答，即每次询问的难度值，每次回答用换行隔开

样例输入

5 4

3 2 4 -3 1

2 3 4

1 1 4 1

1 2 3 -3

2 3 4

样例输出

1

0

提示

对于50%的数据，$N<=1000,M<=1000$；

对于100%的数据，$N<=200000,M<=200000 |P|<=50000$；

每个知识点难度值$|A_i|<=50000$;

附洛谷原题：

1.线段树 模板1

2.线段树 模板2 进击版

3.庙会班车 聪明题

算法实现&代码实现

采用二分的方法来进行区间信息维护。形成一棵树。

修改复杂度：$O(log_2n)$

查找复杂度：$O(log_2n)$

建树

首先，要建树才能对线段树进行操作。

利用二分-递归-回溯的思想。

递归时，需要三个量：

左端点，右端点，节点编号(像堆一样传递)。

也就是说，若父亲节点为$n$，

左儿子就为$2\times n$

右儿子就为$2\times n+1$

卡常写法：n<<1 n<<1|1

scanf("%d%d",&n,&T);

for(int i=1;i<=n;i++)

scanf("%d",&a[i]);

build(1,n,1);

就这样

void up(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; }

void build(int l,int r,int rt){//up是累加函数

if(l==r){

sum[rt]=a[l];

return;

}

int m=(l+r)>>1;//卡常

build(l,m,rt<<1);

build(m+1,r,rt<<1|1);

up(rt);

return;

}

查找

然后是查找，与建树一样，采用二分-递归-回溯的写法

int find(int l,int r,int rt){

if(head<=l&&tail>=r)//head，tail是范围

return sum[rt];//两个变量在主函数内输入

int m=(l+r)>>1;

int s=0;

if(head<=m) s+=find(l,m,rt<<1);//递归查找左子树

if(tail>m) s+=find(m+1,r,rt<<1|1);//递归查找右子树

return s;

}

重头戏----修改

像分块一样，我们用一个懒惰标记 $f$ 数组来保存修改的量。

还是二分修改

void update(int l,int r,int rt){

if(head<=l&&tail>=r){

f[rt]+=v;//head，tail是范围 v是增值

sum[rt]+=v*(r-l+1);//三个变量在主函数内输入

return;

}

int m=(l+r)>>1;

if(head<=m) update(l,m,rt<<1);//左右查找

if(tail>m) update(m+1,r,rt<<1|1);

up(rt);//累加

return;

}

但是

注意，如果 $f_1$ 被修改了，那么， $f_2,f_3$ 也应该修改，所以，我们需要下推标记。

void down(int rt,int l,int r){

if(f[rt]){//l 是左子树的长度，r 是右子树的长度

f[rt<<1]+=f[rt];//要用+=，因为f[rt<<1]可能不等于0

f[rt<<1|1]+=f[rt];//同上

sum[rt<<1]+=f[rt]*l;//sum累加

sum[rt<<1|1]+=f[rt]*r;//sum累加

f[rt]=0;//标记已经下推，标记清零

}

return;

}

但是，在搜索的时候，也要下推标记，不然。。。

所以正确的修改和搜索是这样的：

int find(int l,int r,int rt){

if(head<=l&&tail>=r)

return sum[rt];

int m=(l+r)>>1;

down(rt,m-l+1,r-m);//递归搜索前下推标记

int s=0;

if(head<=m) s+=find(l,m,rt<<1);

if(tail>m) s+=find(m+1,r,rt<<1|1);

return s;

}

void update(int l,int r,int rt){

if(head<=l&&tail>=r){

f[rt]+=v;

sum[rt]+=v*(r-l+1);

return;

}

int m=(l+r)>>1;

down(rt,m-l+1,r-m);//查找前下推标记

if(head<=m) update(l,m,rt<<1);

if(tail>m) update(m+1,r,rt<<1|1);

up(rt);

return;

}

模板

这个模板，除掉主函数什么的，有$x$行$(x>40)$。

最后希望大家使用自己的码风，创建一份自己的代码，背下来，尽量在10分钟之内打出来(因为考的一般不是模板)。

#include

#define maxn 200001

using namespace std;

int sum[maxn<<2],a[maxn],n,T,f[maxn<<2];

int head,tail,v,k;

void up(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; }

void build(int,int,int);

int find(int,int,int);

void down(int,int,int);

void update(int,int,int);

int main(){

scanf("%d%d",&n,&T);

for(int i=1;i<=n;i++)

scanf("%d",&a[i]);

build(1,n,1);

while(T--){

scanf("%d",&k);

if(k==1){//修改

scanf("%d%d%d",&head,&tail,&v);

update(1,n,1);

}

else{//查询

scanf("%d%d",&head,&tail);

printf("%d\n",find(1,n,1));

}

}

return 0;

}

void build(int l,int r,int rt){

if(l==r){

sum[rt]=a[l];

return;

}

int m=(l+r)>>1;

build(l,m,rt<<1);

build(m+1,r,rt<<1|1);

up(rt);

return;

}

int find(int l,int r,int rt){

if(head<=l&&tail>=r)

return sum[rt];

int m=(l+r)>>1;

down(rt,m-l+1,r-m);

int s=0;

if(head<=m) s+=find(l,m,rt<<1);

if(tail>m) s+=find(m+1,r,rt<<1|1);

return s;

}

void down(int rt,int l,int r){

if(f[rt]){

f[rt<<1]+=f[rt];

f[rt<<1|1]+=f[rt];

sum[rt<<1]+=f[rt]*l;

sum[rt<<1|1]+=f[rt]*r;

f[rt]=0;

}

return;

}

void update(int l,int r,int rt){

if(head<=l&&tail>=r){

f[rt]+=v;

sum[rt]+=v*(r-l+1);

return;

}

int m=(l+r)>>1;

down(rt,m-l+1,r-m);

if(head<=m) update(l,m,rt<<1);

if(tail>m) update(m+1,r,rt<<1|1);

up(rt);

return;

}

原题解析

但是，如果用这个代码交上去的话。。。

因为这题数据会炸int，所以，我们需要把一些地方改成$long long$，还要加几个$(longlong)$，尤其是乘法，不然会按照int的方式来计算。。。依然如旧

AC代码：耗尽$n$个月才A的,$(n>3)$

#include

#define maxn 200001

using namespace std;

long long sum[maxn<<2],f[maxn<<2];

int head,tail,v,k,a[maxn],n,T;

void up(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; }

void build(int,int,int);

long long find(int,int,int);

void down(int,int,int);

void update(int,int,int);

int main(){

scanf("%d%d",&n,&T);

for(int i=1;i<=n;i++)

scanf("%d",&a[i]);

build(1,n,1);

while(T--){

scanf("%d",&k);

if(k==1){//修改

scanf("%d%d%d",&head,&tail,&v);

update(1,n,1);

}

else{//查询

scanf("%d%d",&head,&tail);

printf("%lld\n",find(1,n,1));

}

}

return 0;

}

void build(int l,int r,int rt){

if(l==r){

sum[rt]=a[l];

return;

}

int m=(l+r)>>1;

build(l,m,rt<<1);

build(m+1,r,rt<<1|1);

up(rt);

return;

}

long long find(int l,int r,int rt){

if(head<=l&&tail>=r)

return sum[rt];

int m=(l+r)>>1;

down(rt,m-l+1,r-m);

long long s=0;

if(head<=m) s+=find(l,m,rt<<1);

if(tail>m) s+=find(m+1,r,rt<<1|1);

return s;

}

void down(int rt,int l,int r){

if(f[rt]){

f[rt<<1]+=f[rt];

f[rt<<1|1]+=f[rt];

sum[rt<<1]+=f[rt]*(long long)l;

sum[rt<<1|1]+=f[rt]*(long long)r;

f[rt]=0;

}

return;

}

void update(int l,int r,int rt){

if(head<=l&&tail>=r){

f[rt]+=v;

sum[rt]+=(long long)v*(long long)(r-l+1);

return;

}

int m=(l+r)>>1;

down(rt,m-l+1,r-m);

if(head<=m) update(l,m,rt<<1);

if(tail>m) update(m+1,r,rt<<1|1);

up(rt);

return;

}