dw建设网站,浏览有关小城镇建设的网站,wordpress设置积分,苏州虎丘区建设局网站线段树是一种二叉搜索数#xff0c;一般用来实现动态的区间询问#xff0c;与树状数组有相似之处#xff0c;但是能用树状数组实现的操作都能用线段树实现。
一般线段树用于以下几种操作#xff1a;
建树#xff0c;单点修改#xff0c;区间查询#xff0c;区间修改。…线段树是一种二叉搜索数一般用来实现动态的区间询问与树状数组有相似之处但是能用树状数组实现的操作都能用线段树实现。
一般线段树用于以下几种操作
建树单点修改区间查询区间修改。
首先要进行的就是建树
void bui(int id,int l,int r)
{if(lr){tr[id]a[l];return ;}int mid(lr)/2;bui(id*2,l,mid);bui(id*21,mid1,r);tr[id]max(tr[id*2],tr[id*21]);//tr[id]tr[id*2]tr[id*21];
}//查询最大值与区间和最小值同理
单点修改
void gexi(int id,int l,int r,int x,int v)
{if(lr){tr[id]v;return ;}int mid(lr)/2;if(xmid)gexi(id*2,l,mid,x,v);else gexi(id*21,mid1,r,x,v);tr[id]max(tr[id*2],tr[id*21]);//tr[id]tr[id*2]tr[id*21]
}//查询最大值与区间和
区间查询
int find(int id,int l,int r,int x,int y)
{if(xlry){return tr[id];}int mid(lr)/2,ans0;if(xmid)ansmax(ans,find(id*2,l,mid,x,y));//ansfind(id*2,l,mid,x,y);if(ymid)ansmax(ans,find(id*21,mid1,r,x,y));//ansfind(id*21,mid1,r,x,y);return ans;
}
区间修改
void push_up(int id)
{tr[id]tr[id*2]tr[id*21];
}
void push_down(int id,int l,int r)
{if(lazy[id])//如果有lazy标记 {int mid(lr)/2;lazy[id*2]lazy[id];//左孩子的lazy加上它的lazy lazy[id*21]lazy[id];//右孩子的lazy加上它的lazy tr[id*2]lazy[id]*(mid-l1);tr[id*21]lazy[id]*(r-mid);lazy[id]0;//清除lazy标记 }
}
void qjgx(int id,int l,int r,int x,int y,int v)
{if(xlry)//[l,r]被[x,y]包含了 }{lazy[id]v;//暂时不下传修改的值加进lazy标记 tr[id]v*(r-l1); return ;}push_down(id,l,r);//要更新节点了开始下传修改的值 int mid(lr)/2;if(xmid)qjgx(id*2,l,mid,x,y,v);//只有xmid(即[l,mid]有一部分是被[x,y]覆盖了的)才需要去更新[l,mid]if(ymid)qjgx(id*21,mid1,r,x,y,v);push_up(id); //子节点更新后父节点也更新
}
下面是两道例题可以试着尝试一下这几种操作
一敌兵布阵 敌人有 N 个工兵营地编号 1∼N。 初始时第 i 个营地有 ai 个人。 接下来有若干个命令命令有 4 种形式 Add i ji 和 j 为正整数表示第 i 个营地增加 j 个人。j 不超过 30 Sub i ji 和 j 为正整数表示第 i 个营地减少 j 个人。j 不超过 30 Query i ji 和 j 为正整数i≤j表示询问第 i 到第 j 个营地的总人数。 End表示结束此命令只会作为最后一条命令出现。 请你计算每个 Query 的答案。 输入格式 第一行包含整数 T表示共有 T 组测试数据。 每组数据第一行包含一个整数 N。 第二行包含 N 个整数 a1,a2,…,aN。 接下来若干行每行包含一条命令格式如题目所述。 输出格式 对于第 i 组数据首先输出一行 Case i:然后对于每个 Query 询问输出一行一个整数表示询问的段中的总人数。 数据范围 1≤T≤10, 1≤N≤50000, 1≤ai≤50, 每组数据最多有 40000 条命令 保证任何营地的人数都不会减少为负数。 输入样例
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End输出样例
Case 1:
6
33
59
AC代码
#include bits/stdc.h
using namespace std;
#define p 50010
int tr[4*p],a[4*p];
void bui(int id,int l,int r)
{if(lr){tr[id]a[l];return ;}int mid(lr)/2;bui(id*2,l,mid);bui(id*21,mid1,r);tr[id]tr[id*2]tr[id*21];
}
int find(int id,int l,int r,int x,int y)
{if(xlry){return tr[id];}int mid(lr)/2,ans0;if(xmid)ansfind(id*2,l,mid,x,y);if(ymid)ansfind(id*21,mid1,r,x,y);return ans;
}
void gexi(int id,int l,int r,int x,int v)
{if(lr){tr[id]v;return ;}int mid(lr)/2;if(xmid)gexi(id*2,l,mid,x,v);else gexi(id*21,mid1,r,x,v);tr[id]tr[id*2]tr[id*21];
}
int main()
{int t;scanf(%d,t);for(int k1;kt;k){int n;scanf(%d,n);memset(a,0,sizeof(a));memset(tr,0,sizeof(tr));for(int i1;in;i)scanf(%d,a[i]);bui(1,1,n);char x[10];int aa,bb,cc;coutCase k:endl;while(~scanf(%s,x)){if(x[0]Q){scanf(%d%d,aa,bb);printf(%d\n,find(1,1,n,aa,bb));}else if(x[0]A){scanf(%d%d,aa,bb);gexi(1,1,n,aa,bb);}else if(x[0]S){scanf(%d%d,aa,bb);gexi(1,1,n,aa,-bb);}elsebreak;}}return 0;
}
二一个简单的整数问题2 给定一个长度为 N 的数列 A以及 M 条指令每条指令可能是以下两种之一 C l r d表示把 A[l],A[l1],…,A[r] 都加上 d。 Q l r表示询问数列中第 l∼r 个数的和。 对于每个询问输出一个整数表示答案。 输入格式 第一行两个整数 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 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4输出样例
4
55
9
15
AC代码
#include bits/stdc.h
#define int long long
using namespace std;
int sumv[10000001],n,m,a[10000001],lazy[10000001];
void push_up(int id)
{sumv[id] sumv[id * 2] sumv[id * 2 1];
}
void push_down(int id,int l,int r)
{if(lazy[id]){int mid (l r) / 2;lazy[id * 2] lazy[id];lazy[id * 2 1] lazy[id];sumv[id * 2] lazy[id] * (mid - l 1);sumv[id * 2 1] lazy[id] * (r - mid);lazy[id] 0;}
}
void bui(int id,int l,int r)
{if(l r){sumv[id] a[l];return ;}int mid (l r) / 2;bui(id * 2,l,mid);bui(id * 2 1,mid 1,r);sumv[id] sumv[id * 2] sumv[id * 2 1];
}
void qjgx(int id,int l,int r,int x,int y,int v)
{if(l x r y){lazy[id] v;sumv[id] v * (r - l 1);return ;}push_down(id,l,r);int mid (l r) / 2;if(x mid) qjgx(id * 2,l,mid,x,y,v);if(y mid) qjgx(id * 2 1,mid 1,r,x,y,v);push_up(id);
}
int find(int id,int l,int r,int x,int y)
{if(x l r y) return sumv[id];push_down(id,l,r);int mid (l r) / 2,ans 0;if(x mid) ans find(id * 2,l,mid,x,y);if(y mid) ans find(id * 2 1,mid 1,r,x,y);return ans;
}
signed main()
{cinnm;for(int i 1; i n; i) cina[i];bui(1,1,n);while(m--){string p;int k,x,y;cinpxy;if(p C){cink;qjgx(1,1,n,x,y,k);}else coutfind(1,1,n,x,y)\n;}return 0;
}
下一篇 codeforces round 885 (div. 2)
