上一次我们讲到线段树的概念和建树，今天，我们来讲线段树的单点修改与区间询问。
1.单点修改
单点修改会改变它所在子树的节点，当你修改了叶节点后，一定要更新其祖先的值。
code:
void up(int p){ s[p] = s[p * 2] + s[p * 2 + 1]; }//向上更新节点 void modify(int p, int l, int r, int x, int v){//p节点编号，l，r区间，v修改值 if (l == r){ s[p] += v; return; } int mid = (l + r) / 2; if (x <= mid) modify(p * 2, l, mid, x, v);//左子树 else modify(p * 2 + 1, mid + 1, r, x, v);//右子树 up(p); }
其实这就是一个模板，记一下，对你有好处！
2.区间询问
一般来说，区间询问是以这样的形式出现滴：
给定一个区间 [ l , r ] ,求区间的和。
上图QAQ
线段树：我又回来啦！
此时，询问 [ 3 , 6 ]的最小值。
先找3所在的区间 [ 1 , 5 ] ,接着在搜左子树，右子树。直到搜到3。
之后在3~6的区间中，[ 4 , 5 ]是一个节点，直接返回区间最小值，不必往下搜，再到右子树上去搜6，找到总区间最小值。
1 int query(int p, int l, int r, int x, int y) 2 { 3 if (x <= l && r <= y) return s[p];//若该结点被查询区间包含 4 int mid = (l + r) / 2, res = 0; 5 if (x <= mid) 6 res += query(p * 2, l, mid, x, y); 7 if (y > mid) 8 res += query(p * 2 + 1, mid + 1, r, x, y); 9 return res; 10 }
这要用到之前的修改
这就是线段树的单点修改与区间查询
自己背一背模板，rp++。