很早之前就学过线段树,但是一直觉得麻烦,没有写过。
今天根据AI的代码,用类封装了一个使用起来还算简单的线段树,方便自己记忆。
class SegmentTree
{vector<int> tree;vector<int> arr;vector<int> lazy;int n;void build(int p,int l,int r){if(l==r){tree[p] = arr[l];return;}int mid = (l+r)/2, lch = p*2, rch = p*2+1;build(lch,l,mid);build(rch,mid+1,r);tree[p] = tree[lch] + tree[rch];}void push_down(int p,int l,int r){if(lazy[p]==0)return;int mid = (l+r)/2, lch = p*2, rch = p*2+1;tree[lch] += lazy[p] * (mid-l+1);lazy[lch] += lazy[p];tree[rch] += lazy[p] * (r-mid);lazy[rch] += lazy[p];lazy[p] = 0;}void update(int p,int l,int r,int ul,int ur,int k){if(l>=ul && r<=ur){lazy[p] += k;tree[p] += k*(r-l+1);return;}push_down(p,l,r);int mid = (l+r)/2, lch = p*2, rch = p*2+1;if(ul<=mid) update(lch,l,mid,ul,ur,k);if(ur>mid) update(rch,mid+1,r,ul,ur,k);tree[p] = tree[lch] + tree[rch];}int query(int p,int l,int r,int ul,int ur){if(ul>r || ur<l)return 0;if(l>=ul && r<=ur)return tree[p];push_down(p,l,r);int mid = (l+r)/2, lch = p*2, rch = p*2+1;return query(lch,l,mid,ul,ur) + query(rch,mid+1,r,ul,ur);}public:SegmentTree(vector<int> &input){n = input.size();tree.resize(4*n);lazy.resize(4*n);arr.resize(n);for(int i=0;i<n;i++)arr[i] = input[i];build(1,0,n-1);}void update(int l,int r,int k){update(1,0,n-1,l,r,k);}int query(int l,int r){return query(1,0,n-1,l,r);}
};
简单说一下这样写的优势有哪些吧。
1.方便记忆。
因为封装在类里,所以每次要写的代码都是一样的,不用根据不同的数组名写不同的代码。
2.方便调用
在public里我定义了调用时用到的函数,减少了p,l,r这几个参数,在主函数里调用的时候就不用想那么多了。
3.不易冲突
如果定义在全局变量,代码功能不仅线段树,可能会和其他部分有冲突。封装在类里,就不会有这个风险。