创作背景
今天是在SMZX的第六天，学习线段树了。所以，当然要写博客好好总结一番。
并不是因为调线段树程序过于烦躁才写的
线段树原理
怎么说呢，其实就是一种变样的深搜。由于本人过于蒟蒻，所以将会用代码来解释
建树
void build(int rt,int l,int r)//rt是当前建树到的节点的下标，l则是左端点，r是右端点
{ if(l == r)//左端点等于右端点意味着什么：说明区间长度为一，所以到了最底下，就是分点。{tree[rt]=a[l];//赋值return ;//退出需要解释吗？}int mid=(l+r)>>1;//等于(l+r)/2build(rt * 2, l , mid);//在沿着左端点下去建build(rt * 2 +1 , mid+1 , r);//在沿着右端点下去建tree[rt]=tree[rt*2]+tree[rt*2+1]; //将2个分点集中在一个根点
}
区间和搜索
做为一个变样的搜索，不能搜索跟废物又什么两样。
int query(int rt, int l, int r, int x, int y)//rt是树的下标，l则是左端点，r是右端点，x是区间的左端点，y是区间的右端点
{if (y < l || r < x) return 0;//如果目标区间在搜索区间之外，退出if (x <= l && r <= y) return tree[rt];//如果目标区间覆盖搜索区间，输出int mid = (l + r) >> 1;//咳咳，不必多说了吧return query(rt * 2, l, mid, x, y) + query(rt * 2 + 1, mid + 1, r, x, y);//输出和
}
区间替换
估计有读者要问：为什么我不先写单点替换。看看程序，你就知道了。（本处为加上某个数）
void update(int rt, int l, int r, int x, int y, int val)//rt是树的下标，l则是左端点，r是右端点，x是区间的左端点，y是区间的右端点,val是加的值
{if (y < l || x > r) return;//如果目标区间在搜索区间之外，退出if (x <= l && r <= y) {tree[rt] += val * (r - l + 1);//求新的区间和tag[rt] += val;//这里就是lazy标记，是要记录出那个要修改的数字,在区间查询的时候再根据标记来修改。return;}int mid = (l + r) >> 1;down(rt, l, mid, r);//下毒 逃~ lazy标记update(rt * 2, l, mid, x, y, val);//左端点搜索一遍update(rt * 2 + 1, mid + 1, r, x, y, val);//右端点搜索一遍tree[rt] = tree[rt * 2] + tree[rt * 2 + 1];//将2个分点集中在一个根点
}
现在我可以告诉你为什么不先写单点替换？因为：
刚刚提到的lazy标记又是何方神圣？来，我们慢慢讲
void down(int rt, int l, int mid, int r)
{int val = tag[rt];//记录lazy标记tag[rt] = 0;//初始化tree[rt * 2] += val * (mid - l + 1)//赋值给左端点tag[rt * 2] += val;;//左端点继承lazy标记tree[rt * 2 + 1] += val * (r - mid);//赋值给右端点tag[rt * 2 + 1] += val; //右端点继承lazy标记
}
The End
读到这里，你以为你会线段树了吗？太天真了，一做题，你就会发现：
不说了，溜了溜了