首页 > 代码库 > 线段树模板整理
线段树模板整理
一、点修改：
二、区间修改：
（1）区间中每点值直接修改为v。
sum = 0;ma = 0;mi = INT_INF;query(x, y, 1, 1, N);
代码如下：
int sumv[MAXN << 2], maxv[MAXN << 2], minv[MAXN << 2], setv[MAXN << 2];int sum, ma, mi;void maintain(int id, int L, int R){ int lc = id << 1, rc = id << 1 | 1; if(R > L){ sumv[id] = sumv[lc] + sumv[rc]; maxv[id] = max(maxv[lc], maxv[rc]); minv[id] = min(minv[lc], minv[rc]); } if(setv[id] >= 0){ minv[id] = maxv[id] = setv[id]; sumv[id] = setv[id] * (R - L + 1); }}void pushdown(int id){ int lc = id << 1, rc = id << 1 | 1; if(setv[id] >= 0){ setv[lc] = setv[rc] = setv[id]; setv[id] = -1; }}void update(int l, int r, int id, int L, int R, int v){//l,r要询问的区间 int lc = id << 1, rc = id << 1 | 1; if(l <= L && r >= R){ setv[id] = v; } else{ pushdown(id); int Mid = L + (R - L) / 2; if(l <= Mid) update(l, r, lc, L, Mid, v); else maintain(lc, L, Mid); if(r > Mid) update(l, r, rc, Mid + 1, R, v); else maintain(rc, Mid + 1, R); } maintain(id, L, R);}void query(int l, int r, int id, int L, int R){//l,r要询问的区间 if(setv[id] >= 0){ sum += setv[id] * (min(R, r) - max(L, l) + 1); ma = max(ma, setv[id]); mi = min(mi, setv[id]); } else if(l <= L && r >= R){ sum += sumv[id]; ma = max(ma, maxv[id]); mi = min(mi, minv[id]); } else{ int Mid = L + (R - L) / 2; if(l <= Mid) query(l, r, id << 1, L, Mid); if(r > Mid) query(l, r, id << 1 | 1, Mid + 1, R); }}
线段树模板整理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。