首页 > 代码库 > 搬运——线段树模板
搬运——线段树模板
最近各种线段树，然后一直用HH模板！然后老是写不出！
与之搬运过来！
线段树功能:update:单点增减 query:区间求和
#include <cstdio> #define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 55555;int sum[maxn<<2];void PushUP(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void build(int l,int r,int rt) { if (l == r) { scanf("%d",&sum[rt]); return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUP(rt);}void update(int p,int add,int l,int r,int rt) { if (l == r) { sum[rt] += add; return ; } int m = (l + r) >> 1; if (p <= m) update(p , add , lson); else update(p , add , rson); PushUP(rt);}int query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return sum[rt]; } int m = (l + r) >> 1; int ret = 0; if (L <= m) ret += query(L , R , lson); if (R > m) ret += query(L , R , rson); return ret;}int main() { int T , n; scanf("%d",&T); for (int cas = 1 ; cas <= T ; cas ++) { printf("Case %d:\n",cas); scanf("%d",&n); build(1 , n , 1); char op[10]; while (scanf("%s",op)) { if (op[0] == ‘E‘) break; int a , b; scanf("%d%d",&a,&b); if (op[0] == ‘Q‘) printf("%d\n",query(a , b , 1 , n , 1)); else if (op[0] == ‘S‘) update(a , -b , 1 , n , 1); else update(a , b , 1 , n , 1); } } return 0;}线段树功能:update:单点替换 query:区间最值
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 #define lson l , m , rt << 1 6 #define rson m + 1 , r , rt << 1 | 1 7 const int maxn = 222222; 8 int MAX[maxn<<2]; 9 void PushUP(int rt) {10 MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);11 }12 void build(int l,int r,int rt) {13 if (l == r) {14 scanf("%d",&MAX[rt]);15 return ;16 }17 int m = (l + r) >> 1;18 build(lson);19 build(rson);20 PushUP(rt);21 }22 void update(int p,int sc,int l,int r,int rt) {23 if (l == r) {24 MAX[rt] = sc;25 return ;26 }27 int m = (l + r) >> 1;28 if (p <= m) update(p , sc , lson);29 else update(p , sc , rson);30 PushUP(rt);31 }32 int query(int L,int R,int l,int r,int rt) {33 if (L <= l && r <= R) {34 return MAX[rt];35 }36 int m = (l + r) >> 1;37 int ret = 0;38 if (L <= m) ret = max(ret , query(L , R , lson));39 if (R > m) ret = max(ret , query(L , R , rson));40 return ret;41 }42 int main() {43 int n , m;44 while (~scanf("%d%d",&n,&m)) {45 build(1 , n , 1);46 while (m --) {47 char op[2];48 int a , b;49 scanf("%s%d%d",op,&a,&b);50 if (op[0] == ‘Q‘) printf("%d\n",query(a , b , 1 , n , 1));51 else update(a , b , 1 , n , 1);52 }53 }54 return 0;55 }
线段树功能:update:成段增减 query:区间求和
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 #define lson l , m , rt << 1 6 #define rson m + 1 , r , rt << 1 | 1 7 #define LL long long 8 const int maxn = 111111; 9 LL add[maxn<<2];10 LL sum[maxn<<2];11 void PushUp(int rt) {12 sum[rt] = sum[rt<<1] + sum[rt<<1|1];13 }14 void PushDown(int rt,int m) {15 if (add[rt]) {16 add[rt<<1] += add[rt];17 add[rt<<1|1] += add[rt];18 sum[rt<<1] += add[rt] * (m - (m >> 1));19 sum[rt<<1|1] += add[rt] * (m >> 1);20 add[rt] = 0;21 }22 }23 void build(int l,int r,int rt) {24 add[rt] = 0;25 if (l == r) {26 scanf("%lld",&sum[rt]);27 return ;28 }29 int m = (l + r) >> 1;30 build(lson);31 build(rson);32 PushUp(rt);33 }34 void update(int L,int R,int c,int l,int r,int rt) {35 if (L <= l && r <= R) {36 add[rt] += c;37 sum[rt] += (LL)c * (r - l + 1);38 return ;39 }40 PushDown(rt , r - l + 1);41 int m = (l + r) >> 1;42 if (L <= m) update(L , R , c , lson);43 if (m < R) update(L , R , c , rson);44 PushUp(rt);45 }46 LL query(int L,int R,int l,int r,int rt) {47 if (L <= l && r <= R) {48 return sum[rt];49 }50 PushDown(rt , r - l + 1);51 int m = (l + r) >> 1;52 LL ret = 0;53 if (L <= m) ret += query(L , R , lson);54 if (m < R) ret += query(L , R , rson);55 return ret;56 }57 int main() {58 int N , Q;59 scanf("%d%d",&N,&Q);60 build(1 , N , 1);61 while (Q --) {62 char op[2];63 int a , b , c;64 scanf("%s",op);65 if (op[0] == ‘Q‘) {66 scanf("%d%d",&a,&b);67 printf("%lld\n",query(a , b , 1 , N , 1));68 } else {69 scanf("%d%d%d",&a,&b,&c);70 update(a , b , c , 1 , N , 1);71 }72 }73 return 0;74 }
搬运——线段树模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。