营销型网站建设目的和意义,科技企业网站源码,wordpress免费主题推荐,如何制作简易个人网站数据结构#xff08;终极线段树篇#xff09;
摘要#xff1a; 问题的提出#xff1a;如何解决多样化的区间操作问题#xff1f; solve#xff1a;线段树#xff01;#xff01;#xff01; 关键字#xff1a; 线段树#xff0c;可持久化线段树#xff0c;权值线段…数据结构终极线段树篇
摘要 问题的提出如何解决多样化的区间操作问题 solve线段树 关键字 线段树可持久化线段树权值线段树线段树森林动态开点线段树区间操作线段树应用。 前言 区间操作问题的解决方法极多如树状数组RMQ等。 所有这些数据结构都具有一定的局限性都具有各自的优势和劣势。 而线段树无疑是这些数据结构中性价比最高的数据结构Ps搞什么线段树暴力出奇迹啊 线段树线段树线段树。 顾名思义树上每一个节点表示一个线段区间每一次对一整个线段区间进行操作棒棒。 第1节讲述了线段树的基本性质。 第2节实现了基本线段树。 第3节讲述动态开点线段树。 第4节讲述权值线段树。 //第5节讲述线段树森林。 //第6节讲述线段树的重要应用和例题。 1.线段树的基本性质 1.0基本线段树的性质 1.每个节点u表示一个区间[l,r]。若节点u非叶子节点则u有两个儿子。设midlr/2。 左儿子为[l,mid]节点编号为u*2。 右儿子为[mid1,r]节点编号为u*21。 2.线段树的深度为O(lgn) 3.线段树的节点个数为On常数约为4。 4.线段树上任意一个区间[l,r]都可以被Ologn个线段覆盖。 思考为何左儿子不为[l,mid1]为何左儿子的节点编号为u*2。 思考如何证明线段树的节点个数为On且常数为4。 思考如何证明线段树上任意一个区间[l,r]都可以被Ologn个线段覆盖。 倘若我们只需要单点修改我们只需要找到相应的叶子节点更改叶子节点并沿路更新。 但倘若我们需要区间修改我们却需要引入lazy tag懒惰标记。 每一次操作都先下放懒标记清空标记再进行相应的操作。 如上图若将[1,5]全加上3。 需要标记tag[1,5]3下一次操作到[1,5]时下放。 tag[1,3]3,tag[4,5]3,tag[1,5]0,sum[1,5]3*5 2.基本线段树的实现 2.1基本线段树的区间加询问区间和
#includebits/stdc.h
#define ll long long
using namespace std;
const int MAXN1000005;
ll a[MAXN];
ll read()
{char cgetchar(); ll f1,x0;while (!isdigit(c)) {if (c-) f-1; cgetchar();}while (isdigit(c)) {xx*10c-0; cgetchar();}return f*x;
}
struct Segment_tree
{struct node{int l,r;ll sum,tag;} tree[MAXN2];void up(int x){ tree[x].sumtree[x1].sumtree[(x1)|1].sum; }void down(int x){int num1(tree[x1].r-tree[x1].l1);int num2(tree[(x1)|1].r-tree[(x1)|1].l1);tree[(x1)|1].sumtree[x].tag*num2; tree[x1].tagtree[x].tag; tree[(x1)|1].tagtree[x].tag; tree[x1].sumtree[x].tag*num1; tree[x].tag0;}void build(int x,int l,int r,ll *a){tree[x].ll;tree[x].rr;if (lr){tree[x].suma[l];tree[x].tag0;return;}int mid(lr)1;build(x1,l,mid,a);build((x1)|1,mid1,r,a);up(x);}void change(int x,int l,int r,ll y){if (tree[x].lltree[x].rr){tree[x].tagy;tree[x].sumy*(tree[x].r-tree[x].l1);return;}down(x);int mid(tree[x].ltree[x].r)1;if (rmid) change(x1,l,r,y);else if (lmid) change((x1)|1,l,r,y);else {change(x1,l,mid,y);change((x1)|1,mid1,r,y);}up(x);}ll query(int x,int l,int r){if (tree[x].lltree[x].rr) return tree[x].sum;down(x);int mid(tree[x].ltree[x].r)1;if (rmid) return query(x1,l,r);else if (lmid) return query((x1)|1,l,r);else return query(x1,l,mid)query((x1)|1,mid1,r);}void print(int x){for (int i1;ix;i) printf(%d %d %d\n,tree[i].l,tree[i].r,tree[i].sum);printf(\n);}
} segment_tree;
int main()
{int nread(),mread();for (int i1;in;i) a[i]read();segment_tree.build(1,1,n,a);for (int i1;im;i){int cread();if (c1){int xread(),yread(),zread();segment_tree.change(1,x,y,z);}else{int xread(),yread();printf(%lld\n,segment_tree.query(1,x,y));}}return 0;
} 3.动态开点线段树 动态开点线段树实现单点加区间求和。
#includebits/stdc.h
#define ll long long
using namespace std;
const int MAXN1000005; const int MAXS1e9;
ll read()
{char cgetchar(); ll f1,x0;while (!isdigit(c)) {if (c-) f-1; cgetchar();}while (isdigit(c)) {xx*10c-0; cgetchar();}return f*x;
}
struct Dynamic_segment_tree
{int nodenum0;struct node{int l,r,leftnode,rightnode;ll sum;} tree[MAXN2];void change(int x,int l,int r,int t,ll y){if (!x){nodenum;xnodenum;}tree[x].ll;tree[x].rr;tree[x].sumy;if (lr) return;int mid(tree[x].ltree[x].r)1;if (tmid) change(tree[x].leftnode,l,mid,t,y);else change(tree[x].rightnode,mid1,r,t,y);}ll query(int x,int l,int r){if (!x) return 0;if (tree[x].lltree[x].rr) return tree[x].sum;int mid(tree[x].ltree[x].r)1;if (rmid) return query(tree[x].leftnode,l,r);else if (lmid) return query(tree[x].rightnode,l,r);else return query(tree[x].leftnode,l,mid)query(tree[x].rightnode,mid1,r);}void print(int x){for (int i1;ix;i) printf(%d %d %d %d %d\n,tree[i].l,tree[i].r,tree[i].leftnode,tree[i].rightnode,tree[i].sum);printf(\n);}
} dynamic_segment_tree;
int main()
{int nread(),mread(),root0;for (int i1;im;i){int cread(),xread(),yread();if (c1) dynamic_segment_tree.change(root,1,MAXS,x,y);else printf(%d\n,dynamic_segment_tree.query(root,x,y));//dynamic_segment_tree.print(20);}return 0;
}4.权值线段树
权值线段树就是每一个线段树的叶子节点记录一种值的信息常用于记录区间内某权值的出现个数。
这和一般的线段树差不多只是节点的意义不同。
例题求逆序对个数 未完待续
