首页 > 代码库 > 线段树练习题（不断更新中）
线段树练习题（不断更新中）
通过参考大神们线段树的文章，准备开始要一个一个把上面的题目做一遍了，有很多都是原来做过的，现在也再次做一遍方便以后查阅
打过 * 的表示对别人的想法有所参考，留待以后再做一次
现在比起一开始接触线段树已经更为容易理解了，想到自己暑期集训的时候还是傻傻的背着线段树的格式在做题，不肯动脑子去思考
代码含义，觉得自己会背格式就足够了，后来也一直只会套模版题稍微一变就傻了，现在想想当时懒得动脑筋确实是一个笑话
现在想想最简单来看就是把线段树看成一个能够维护一些自己所需数据的二叉树，通过所维护的数据来判断自己是否需要向下维护左子树
和右子树记得回溯即可
HDU 1166 敌兵布阵
单点增减，区间和查询
线段树：
#include <cstdio>#include <cstring>using namespace std;const int N = 50005;#define ls o<<1#define rs o<<1|1int a[N];char s[10];struct Tree{ int l , r , sum;}tree[N<<2];void build(int o , int l , int r){ int m = (l + r) >> 1; tree[o].l = l , tree[o].r = r; if(l == r){ tree[o].sum = a[l]; return ; } build(ls , l , m); build(rs , m+1 , r); tree[o].sum = tree[ls].sum + tree[rs].sum;}void update(int o , int i , int j , int op){ if(tree[o].l == tree[o].r && tree[o].r == i){ if(op == 1) tree[o].sum += j; if(op == 2) tree[o].sum -= j; return ; } int m = (tree[o].l + tree[o].r) >> 1; if(m >= i) update(ls , i , j , op); if(m+1 <= i) update(rs , i , j , op); tree[o].sum = tree[ls].sum + tree[rs].sum;}int query(int o , int s , int t){ if(tree[o].l >= s && tree[o].r <= t) return tree[o].sum; int m = (tree[o].l + tree[o].r) >> 1; int ans = 0; if(m >= s) ans += query(ls , s , t); if(m+1 <= t) ans += query(rs , s , t); return ans;}int main(){ // freopen("a.in" , "r" , stdin); int T , cas = 0; scanf("%d" , &T); while(T--){ int n , aa , bb; scanf("%d" , &n); for(int i = 1 ; i<=n ; i++) scanf("%d" , &a[i]); build(1 , 1 , n); printf("Case %d:\n" , ++cas); while(scanf("%s" , s)) { if(s[0] == ‘E‘) break; scanf("%d%d" , &aa , &bb); if(s[0] == ‘A‘) update(1 , aa , bb , 1); else if(s[0] == ‘S‘) update(1 , aa , bb , 2); else printf("%d\n" , query(1 , aa , bb)); } } return 0;}堆序列：
#include <cstdio>#include <cstring>using namespace std;const int N = 50005;int a[N] , sum[N<<2] , k;char s[10];void build(int n){ memset(sum , 0 , sizeof(sum)); k = 1; while(k < n+2) k<<=1; for(int i = 1 ; i<=n ; i++) sum[k+i] = a[i]; for(int i = k-1 ; i>=1 ; i--) sum[i] = sum[i<<1] + sum[i<<1|1];}void update(int o){ for(int i = o ; i^1 ; i>>=1) sum[i>>1] = sum[i] + sum[i^1];}int query(int s , int t){ int i = k+s-1 , j = k+t+1; int ans = 0; for(; i^j^1 ; i>>=1 , j>>=1){ if(~i & 1) ans += sum[i^1]; if(j & 1) ans += sum[j^1]; } return ans;}int main(){ // freopen("a.in" , "r" , stdin); int T , cas = 0; scanf("%d" , &T); while(T--){ int n , aa , bb; scanf("%d" , &n); for(int i = 1 ; i<=n ; i++) scanf("%d" , &a[i]); build(n); printf("Case %d:\n" , ++cas); while(scanf("%s" , s)) { if(s[0] == ‘E‘) break; scanf("%d%d" , &aa , &bb); if(s[0] == ‘A‘){ sum[aa+k] += bb; update(aa+k); } else if(s[0] == ‘S‘){ sum[aa+k] -= bb; update(aa+k); } else printf("%d\n" , query(aa , bb)); } } return 0;}HDU 1754
老师对学生成绩的更新，找某一区间内学生成绩的最大值
线段树：
#include <cstdio>#include <cstring>using namespace std;#define ls o<<1#define rs o<<1|1const int N = 200005;int score[N] , maxn[N<<2] , ans;char s[5];void build(int o , int l , int r){ if(l == r){ maxn[o] = score[l]; return ; } int m = (l+r)>>1; build(ls , l , m); build(rs , m+1 , r); maxn[o] = maxn[ls] > maxn[rs] ? maxn[ls] : maxn[rs];}void update(int o , int l , int r , int i , int v){ if(l == r && r == i){ maxn[o] = v; return ; } int m = (l+r) >> 1; if(m >= i) update(ls , l , m , i , v); if(m < i) update(rs , m+1 , r , i , v); maxn[o] = maxn[ls] > maxn[rs] ? maxn[ls] : maxn[rs];}void query(int o , int l , int r , int s , int t){ if(l >= s && r<=t){ ans = ans > maxn[o] ? ans : maxn[o]; return; } int m = (l+r) >> 1; if(m >= s) query(ls , l , m , s , t); if(m < t) query(rs , m+1 , r , s , t);}int main(){ // freopen("a.in" , "r" , stdin); int n , m , a , b; while(~scanf("%d%d" , &n , &m)) { for(int i = 1; i<= n ;i++) scanf("%d" , score+i); build(1 , 1 , n); for(int i = 0 ; i<m ; i++) { scanf("%s%d%d" , s , &a , &b); if(s[0] == ‘U‘) update(1 , 1 , n , a , b); else{ ans = 0; query(1 , 1 , n , a , b); printf("%d\n" , ans); } } } return 0;}堆序列：
#include <cstdio>#include <cstring>using namespace std;const int N = 200005;int maxn[N<<2] , D , score[N];char s[5];void build(int n){ D = 1; memset(maxn , 0 , sizeof(maxn)); while(D < n+2) D <<= 1; for(int i = 1 ; i<=n ; i++) maxn[D+i] = score[i]; for(int i = D-1 ; i>=1 ; i--) maxn[i] = maxn[i<<1] > maxn[i<<1|1] ? maxn[i<<1] : maxn[i<<1|1];}void update(int o){ for(int i = D + o ; i^1 ; i>>=1) maxn[i>>1] = maxn[i] > maxn[i^1] ? maxn[i] : maxn[i^1];}int query(int a , int b){ int i = D + a - 1 , j = D + b +1; int ans = 0; for(; i^j^1 ; i>>=1 , j>>=1) { if(~i & 1) ans = ans > maxn[i^1] ? ans : maxn[i^1]; if(j & 1) ans = ans > maxn[j^1] ? ans : maxn[j^1]; } return ans;}int main(){ // freopen("a.in" , "r" , stdin); int n , m , a , b; while(~scanf("%d%d" , & n , &m)) { for(int i = 1 ; i<=n ; i++) scanf("%d" , score+i); build(n); for(int i =0 ; i<m ; i++){ scanf("%s%d%d" , s , &a , &b); if(s[0] == ‘U‘) { maxn[D+a] = b; update(a); } else printf("%d\n" , query(a , b)); } } return 0;}HDU 2795 BillBoard
将海报一张张贴在墙上，总希望贴在最上方，然后往最左侧贴
每次输出海报贴在墙上的位置，如果贴不上去输出-1
这里就是关于建立线段树的小问题
实际上h可以取到10^9是没有必要的，h最大也就是n的最大值200000
具体看代码最上方
/*因为每张海报最多只能占据一行，否则贴不上去所以高度h最大取到200000即可，10^9就是吓唬人的所以维护200000行的剩余宽度，每次取最大值*/#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int N = 200005;#define ls o<<1#define rs o<<1|1int maxn[N<<2] , left[N] , w , h;void build(int o , int l , int r , int w){ maxn[o] = w; if(l == r) return; int m = (l+r) >> 1; build(ls , l , m , w); build(rs , m+1 , r , w);}void update(int o , int l , int r , int i , int v){ int m = (l+r) >> 1 ; if(l == r && r == i){ maxn[o] -= v; return; } if(m >= i) update(ls , l , m , i , v); if(m < i) update(rs , m+1 , r , i ,v); maxn[o] = max(maxn[ls] , maxn[rs]);}int query(int o , int l , int r , int v){ if(maxn[o] < v) return -1; if(l == r) return l; int m = (l+r) >> 1; int ans; if(maxn[ls] >= v) ans = query(ls , l , m , v); else ans = query(rs , m+1 , r , v); return ans;}int main(){ // freopen("a.in" , "r" , stdin); int h , w , n; while(~scanf("%d%d%d" , &h , &w , &n)) { int t = min(n , h); build(1 , 1 , t , w); for(int i = 0 ; i<n ; i++) { int a; scanf("%d" , &a); int ans = query(1 , 1 , t , a); printf("%d\n" , ans); if(ans > 0) update(1 , 1 , t , ans , a); } } return 0;}
POJ 2828 插队问题
一个数插到某个位置上，其后面的数字都要往后推移，最后输出整个序列
用线段树维护一个总空位的值
大概思路看代码上方
/*这里的数理解为自己前方有多少个数在自己前面在线段树上记录对应节点的位置总共有多少个空位因为前面的数会受后面的数的影响但是后面的数肯定不收前面的影响所以可以先插入后面的数到固定位置往前不断插入数字，碰到左子树有足够的空位就往左移，如果不够，右移所需位置要减去左侧位置*/#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int N = 200005;#define ls o<<1#define rs o<<1|1int sum[N<<2] , left[N] , id[N] , rec[N] , val[N]; //sum记录这个节点对应的区间还有多少位置void push_up(int o){ sum[o] = sum[ls] + sum[rs];}void build(int o , int l , int r){ if(l == r){ sum[o] = 1; return; } int m = (l+r) >> 1; build(ls , l , m); build(rs , m+1 , r); push_up(o);}void update(int o , int l , int r , int i){ int m = (l+r) >> 1 ; if(l == r && r == i){ sum[o] = 0; return; } if(m >= i) update(ls , l , m , i); if(m < i) update(rs , m+1 , r , i); push_up(o);}int query(int o , int l , int r , int v){ if(l == r) return l; int m = (l+r) >> 1; int ans; if(sum[ls] >= v) ans = query(ls , l , m , v); else ans = query(rs , m+1 , r , v - sum[ls]); return ans;}int main(){ // freopen("a.in" , "r" , stdin); int n; while(~scanf("%d" , &n)) { build(1 , 1 , n); for(int i = 1 ; i<= n ; i++){ scanf("%d%d" , &id[i] , &val[i]); } for(int i = n ; i>=1 ; i--){ int tmp = query(1 , 1 , n , id[i]+1); rec[tmp] = val[i]; update(1 , 1 , n , tmp); } for(int i = 1 ; i<=n ; i++) printf("%d " , rec[i]); puts(""); } return 0;}
*POJ 1394
给定一堆序列，来判断所有i>j , a[i] > a[j]的组数 ， 另外可以不断把收个元素放在后面 ， 这个序列的元素是由0~n-1组成
往往碰到添加 n 个连续序号的题目都可以通过不断将元素添入线段树对应的 i 位置逐个维护
因为是0~n-1所以可以通过一个个添加节点实现，我这里用的是逆向添加节点，每次判断添加元素的前方已经有几个位置放了元素，那么
这么多个位置就可以跟当前添加元素形成的对数
另外每次将首个数放到最后方
减少的是 a[i] - 1 (a[i]从1开始) , 我自己题目为了自己好理解把所有字母 加 了1 ， 本来是从0开始 的
增加的是 n - a[i] ，然后不断更新最小值即可
自己一开始对最后的更新n一直找不到线性的方法还是看了别人的思路得到的，自己还要不断进步啊
#include <cstdio>#include <cstring>#include <iostream>using namespace std;#define ls o<<1#define rs o<<1|1const int N = 50010;int sum[N<<2] , num[N]; //维护线段树上空余节点的总个数void build(int o , int l , int r){ int m = (l+r) >> 1; sum[o] = 0; if(l == r) return; build(ls , l , m); build(rs , m+1 , r);}void update(int o , int l , int r , int i){ int m = (l + r) >> 1; if(l == r && r == i){ sum[o] = 1; return; } if(m >= i) update(ls , l , m , i); else update(rs , m+1 , r , i); sum[o] = sum[o<<1] + sum[o<<1|1];}int query(int o , int l , int r , int i){ int m = (l+r) >> 1; if(r < i) return sum[o]; if(l >= i) return 0; int ans = 0; if(m >= i) ans += query(ls , l , m , i); else ans += query(rs , m+1 , r , i) + sum[ls]; return ans;}int main(){ // freopen("a.in" , "r" , stdin); int n; while(~scanf("%d" , &n)) { int ans = (1<<30) , tmp = 0; build(1 , 1 , n); for(int i = 0 ; i<n ; i++) { scanf("%d" , num+i); num[i]++; } for(int i = n-1 ; i>=0 ; i--){ tmp += query(1 , 1 , n , num[i]); update(1 , 1 , n , num[i]); } ans = min(ans , tmp); for(int i = 0 ; i<n ; i++){ tmp -= num[i]-1; // cout<<"tmp1: "<<tmp<<endl; tmp += n-num[i]; // cout<<"tmp2: "<<tmp<<endl; ans = min(ans , tmp); } printf("%d\n" , ans); } return 0;}
线段树练习题（不断更新中）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。