[模板]线段树的建树、查询、单点更新、区间更新

此线段树以求区间最小值为例，求区间和只需适当更改pushup()函数即可

建树

int arr[N]; int SetTree[N*4]; int pushup(int root) { return min(SetTree[root<<1], SetTree[root<<1|1]); } void build(int root, int left, int right) { if(left == right) { SetTree[root] = arr[left]; return; } int mid = (left + right) >> 1; build(root<<1, left, mid); build(root<<1|1, mid+1, right); SetTree[root] = pushup(root); }查询

int query(int root, int left, int right, int L, int R) { if(L > right || R < left) return 1<<29; if(L <= left && R >= right) return SetTree[root]; int mid = (left + right) >> 1; int l = query(root<<1, left, mid, L, R); int r = query(root<<1|1, mid+1, right, L, R); return min(l, r); }

单点更新

int pushup(int root) { return min(SetTree[root<<1], SetTree[root<<1|1]); } void update(int root, int left, int right, int index, int value) { if(left == right) { if(index == left) SetTree[root] = value; return; } int mid = (left + right) >> 1; if(index <= mid) update(root<<1, left, mid, index, value); else update(root<<1|1, mid+1, right, index, value); SetTree[root] = pushup(root); }

区间更新（注意延迟标记这个概念）

struct{ int val; int mark; }SetTree[N*4]; int pushup(int root) { return SetTree[root<<1].val + SetTree[root<<1|1].val; } //传递延迟标记给子节点 void pushdown(int root, int left, int mid, int right) { if(SetTree[root].mark != 0) { //延迟标记传递 SetTree[root<<1].mark = SetTree[root].mark; SetTree[root<<1|1].mark = SetTree[root].mark; //区间和也要变化 SetTree[root<<1].val = SetTree[root].mark * (mid-left+1); SetTree[root<<1|1].val = SetTree[root].mark * (right-mid); //向下传递后，root的mark清空 SetTree[root].mark = 0; } } //区间更新 void update(int root, int left, int right, int l, int r, int mark) { if(l > right || r < left) return; if(l <= left && r >= right) { SetTree[root].mark = mark; SetTree[root].val = mark * (right-left+1); return; } int mid = (left + right) >> 1; pushdown(root, left, mid, right); update(root<<1, left, mid, l, r, mark); update(root<<1|1, mid+1, right, l, r, mark); SetTree[root].val = pushup(root); } 或者

struct{ int val; int mark; int l;//区间下界 int r;//区间上界 }Tree[N*4]; int pushup(int root) { return Tree[root<<1].val + Tree[root<<1|1].val; } //传递延迟标记给子节点 void pushdown(int root) { if(Tree[root].mark != 0) { int mid = (Tree[root].l + Tree[root].r) >> 1; Tree[root<<1].mark = Tree[root].mark; Tree[root<<1|1].mark = Tree[root].mark; Tree[root<<1].val = Tree[root].mark * (mid-Tree[root].l+1); Tree[root<<1|1].val = Tree[root].mark * (Tree[root].r-mid); Tree[root].mark = 0; } } //区间更新 void update(int root, int l, int r, int value) { if(l > Tree[root].r || r < Tree[root].l) return; if(l <= Tree[root].l && r >= Tree[root].r) { Tree[root].mark = value; Tree[root].val = value * (Tree[root].r-Tree[root].l+1); return; } pushdown(root); update(root<<1, l, r, value); update(root<<1|1, l , r, value); Tree[root].val = pushup(root); }