首页 > 代码库 > 线段树——快速区间查找
线段树——快速区间查找
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。
#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<iomanip>#include<string>#include<climits>#include<cmath>#include<time.h>#define MAX 120000using namespace std;int n,m;int ans;struct Tree{ int l,r; int sum,add;};Tree tree[MAX*3];void pushup(int x){ int tmp=2*x; tree[x].sum=tree[tmp].sum+tree[tmp+1].sum;}void pushdown(int x){ int tmp=2*x; tree[tmp].add+=tree[x].add; tree[tmp+1].add+=tree[x].add; tree[tmp].sum+=tree[x].add*(tree[tmp].r-tree[tmp].l+1); tree[tmp+1].sum+=tree[x].add*(tree[tmp+1].r-tree[tmp+1].l+1); tree[x].add=0;}void build(int l,int r,int x){ tree[x].l=l; tree[x].r=r; tree[x].add=0; if(l==r) { tree[x].sum=0; return ; } int tmp=x<<1; int mid=(l+r)>>1; build(l,mid,tmp); build(mid+1,r,tmp+1); pushup(x);}void update(int l,int r,int c,int x){ if(r<tree[x].l||l>tree[x].r) return ; if(l<=tree[x].l&&r>=tree[x].r) { tree[x].add+=c; tree[x].sum+=c*(tree[x].r-tree[x].l+1); return ; } if(tree[x].add) pushdown(x); int tmp=x<<1; update(l,r,c,tmp); update(l,r,c,tmp+1); pushup(x);}void query(int l,int r,int x){ if(r<tree[x].l||l>tree[x].r) return ; if(l<=tree[x].l&&r>=tree[x].r) { ans+=tree[x].sum; return ; } if(tree[x].add) pushdown(x); int tmp=x<<1; int mid=(tree[x].l+tree[x].r)>>1; if(r<=mid) query(l,r,tmp); else if(l>mid) query(l,r,tmp+1); else { query(l,mid,tmp); query(mid+1,r,tmp+1); }}int main(){ //freopen("input2.txt","r",stdin); //freopen("output2.txt","w",stdout); scanf("%d %d",&n,&m); build(1,n,1);//建树 int str0; while(m--){ scanf("%d",&str0); if(str0==2){ int l; scanf("%d",&l); ans=0; query(l,l,1); printf("%d\n",ans); } else if(str0==1){ int l,r; scanf("%d %d",&l,&r); update(l,r,1,1); } } return 0;}
线段树——快速区间查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。