线段树简介及实现

线段树

一 线段树简介

 线段树是一种数据结构，对于RMQ，RSQ问题可以达到O(log(n))的区间修改,同时还支持多种加乘的操作，是一种常见的数据结构

二 线段树的数据结构

 在这里我们可以设计一个结构体去存储一个节点的信息，有左边界，右边界，懒惰标记，区间内数之和等附加数据功能

对于单点的数据，他的左边界等于右边界

 懒惰标记是我们实现O(logn)区间修改的关键点。即如果我们要修改一个区间内的数，那么我们只要修改管理这个大区间的点即可，没有必要对它管理的分支进行进一步操作，等到下一步需要操作时在将这个懒惰标记向下传导。

三 线段树的代码实现

1数据结构

 struct SergmentNode
{int l;int r;int lazy;int sum;
}elem[N];

2 建树

void bulid(int p,int r,int l)
{elem[p].l = l;elem[p].r = r;if(l==r) elem[p].sum = number[r];else{int mid = (l+r)>>1;bulid(ls(p), l, mid);bulid(rs(p), mid+1, l);elem[p].sum = elem[rs(p)].sum + elem[ls(p)].sum;}
}

3 传导懒惰标记

void spread(int p)
{if(elem[p].lazy){elem[ls(p)].sum += (elem[ls(p)].r - elem[ls(p)].l + 1)*elem[p].lazy;elem[rs(p)].sum += (elem[rs(p)].r - elem[rs(p)].l + 1)*elem[p].lazy;elem[ls(p)].lazy += elem[p].lazy; // 增加标记elem[rs(p)].lazy += elem[p].lazy;elem[p].lazy = 0;// 传导后直接清空慵懒标记}
}

4 区间修改

void update(int p,int l,int r,int add)
{if(l<=elem[p].l&&r>=elem[p].r){elem[p].sum += (elem[p].r - elem[p].l + 1)*add;elem[p].lazy += add;return;}// 如果这个区间被包含在要修改的区间内int mid = (elem[p].r + elem[p].l)>>1;if(l <= mid) update(ls(p), l, r, add);if(r >= mid) update(rs(p), l, r, add);elem[p].sum += elem[ls(p)].sum + elem[rs(p)].sum;// 增加和数
}

5 区间查询

int ask(int p,int l,int r)
{if(l<=elem[p].l&&r>=elem[p].r) return elem[p].sum;spread(p);int mid = (elem[p].r+elem[p].l)>>1;int ans = 0;if(l <= mid) ans+=ask(ls(p), l, r);if(r >= mid) ans+=ask(rs(p), l, r);return ans;
}

写在最后，考试周，写的匆忙，勿怪

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！