这篇文章用来总结三种基础线段树模板。
第一种：
给出N个数，支持以下两种操作
·Q x y求从第x个元素到y元素的和。
M x v将位置为x的元素修改成v。
下面是模板，其中宏定义lson，rson分别为左儿子，右儿子。比较方便。
#include#include #define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define N 500009using namespace std;int w[N<<2|1];void update(int rt){ //更新操作，将左子树与右子树合并 w[rt] = w[rt << 1]+w[rt<<1|1]; }int read(){ //读入优化 int x = 0; char ch = getchar(); while(ch < '0' || ch > '9')ch = getchar(); while(ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x;}void modify(int l,int r,int rt,int p,int v){ //修改操作，将位置为p的元素修改为v if(l == r){ //达到要求要修改的节点，则对它进行修改 w[rt] = v; return; } int m = (l + r)>>1; if(p <= m)modify(lson,p,v); //在左子树上则递归修改左子树 else modify(rson,p,v); //在右子树上则修改右子树 update(rt); //修改完成进行更新 }void build(int l,int r,int rt){ //建树 if(l == r){ //叶子节点 w[rt] = read(); //读入 return; } int m = (l +r)>>1; build(lson); //如果是非叶子节点则分别递归构造左子树与右子树 build(rson); update(rt); //左子树与右子树都已建造完成，进行更新 }int query(int l,int r,int rt,int nowl,int nowr){ //询问操作,询问区间[nowl,nowr] 和 if(nowl <= l && r <= nowr)return w[rt]; //当前节点在所求区间内则返回节点值 int m = (l + r)>>1; int ans = 0; if(nowl <= m)ans += query(lson,nowl,nowr); //左边子树残余范围 if(nowr > m)ans += query(rson,nowl,nowr); //右边 return ans; //返回 }int main(){ int n = read(),m = read(); build(1,n,1); while(m--){ int cmd = read(); if(cmd == 1){ //1为求区间和 int x = read(),y = read(); printf("%d\n",query(1,n,1,x,y)); } else { int x = read(),v = read(); modify(1,n,1,x,v); //2为修改 } } return 0;}
第二种：
给定长度为N的序列，支持以下两种操作。
·Q x y 求区间[x,y]序列的和
·M x y v 将区间[x,y]的每个数加上一个值v。
对于Q操作，我们处理的方法与第一种几乎是别无二致的。
但对于M操作，我们在这用到了打标记的方法。
#include#include #define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define N 50009using namespace std;#ifdef WIN32 //条件编译，使得该程序输出不受不同平台下longlong带来的影响 #define LL "%I64d\n"#else#define LL "%lld\n"#endiflong long w[N<<2|1],add[N<<2|1]; int read(){ int x = 0; char ch = getchar(); while(ch < '0' || ch > '9')ch = getchar(); while(ch >= '0' && ch <= '9'){ x =x * 10 + ch -'0'; ch = getchar(); } return x;}void update(int rt){ w[rt] = w[rt<<1]+w[rt<<1|1];}void build(int l,int r,int rt){ if(l == r){ w[rt] = read(); add[rt] = 0; return; } int m = (l + r)>>1; build(lson); build(rson); update(rt);}void color(int l,int r,int rt,int v){ //对节点进行标记 w[rt] += (r-l+1)*v; add[rt] += v;}void push_col(int l,int r,int rt){ //发放标记 if(add[rt]){ int m = (l+r)>>1; color(lson,add[rt]); color(rson,add[rt]); add[rt] = 0; }}void modify(int l,int r,int rt,int nowl,int nowr,int v){ if(nowl <= l && r <= nowr){ color(l,r,rt,v); return; } push_col(l,r,rt); //发放标记 int m = (l+r)>>1; if(nowl <= m)modify(lson,nowl,nowr,v); if(m < nowr)modify(rson,nowl,nowr,v); update(rt);}long long query(int l,int r,int rt,int nowl,int nowr){ if(nowl <= l && r <= nowr)return w[rt]; push_col(l,r,rt); //发放标记 int m = (l+r)>>1; long long ans = 0; if(nowl <= m)ans += query(lson,nowl,nowr); if(m < nowr)ans += query(rson,nowl,nowr); return ans;}int main(){ int n = read(),m = read(); build(1,n,1); while(m--){ int cmd = read(); if(cmd == 1){ int x = read(),y = read(); printf(LL,query(1,n,1,x,y)); } else{ int x = read(),y = read(),v = read(); modify(1,n,1,x,y,v); } } return 0;}
第三种：
给定长度为N的序列，支持以下操作。
· Q x y 求区间[x,y]的和
· M1 x y v 将区间[x,y]的每个数都乘以v
· M2 x y k 将区间[x,y]的每个数加上k
· M3 x y v k将区间[x,y]的每个数先乘以v再加上k
看代码....
#include#include #define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define N 50009using namespace std;#ifdef WIN32#define LL "%I64d\n"#else#define LL "%lld\n"#endiflong long w[N<<2|1],add[N<<2|1],mul[N<<2|1]; //和 加 乘 int read(){ int x = 0; char ch = getchar(); while(ch < '0' || ch > '9')ch = getchar(); while(ch >= '0' && ch <= '9'){ x = x * 10 + ch -'0'; ch = getchar(); } return x;}void update(int rt){ w[rt] = w[rt<<1] + w[rt<<1|1];}void build(int l,int r,int rt){ add[rt] = 0; mul[rt] = 1; //乘的初始化应为1 if(l == r){ w[rt] = read(); return; } int m = (l+r)>>1; build(lson); build(rson); update(rt);}void color(int l,int r,int rt,int v,int k){ w[rt] = w[rt]*v + (r-l+1)*k; add[rt] = add[rt]*v+k; mul[rt] *=v;}void push_col(int l,int r,int rt){ if(add[rt] || mul[rt] != 1){ int m = (l+r)>>1; color(lson,mul[rt],add[rt]); color(rson,mul[rt],add[rt]); add[rt] = 0; mul[rt] = 1; }}void modify(int l,int r,int rt,int nowl,int nowr,int v,int k){ if(nowl <= l && r <= nowr){ color(l,r,rt,v,k); return; } push_col(l,r,rt); int m = (l+r)>>1; if(nowl <= m)modify(lson,nowl,nowr,v,k); if(m < nowr)modify(rson,nowl,nowr,v,k); update(rt);}long long query(int l,int r,int rt,int nowl,int nowr){ if(nowl <= l && r <= nowr)return w[rt]; push_col(l,r,rt); int m = (l+r)>>1; long long ans = 0; if(nowl <= m)ans += query(lson,nowl,nowr); if(m < nowr)ans += query(rson,nowl,nowr); return ans;}int main(){ int n = read(), m = read(); build(1,n,1); while(m--){ int cmd = read(); if(cmd == 1){ int x = read(),y = read(); printf(LL,query(1,n,1,x,y)); } else if(cmd == 2){ //乘 int x = read(),y = read(),v = read(); modify(1,n,1,x,y,v,0); } else { int x = read(),y = read(),k = read(); modify(1,n,1,x,y,1,k); } } return 0;}