潍坊网站优化培训,石家庄网络平台推广,大同网站建设制作哪家好,app是如何开发出来的线段树是常用来维护 区间信息 的数据结构
线段树可以在 O(logN) 的时间复杂度内实现
单点修改区间修改区间查询 区间求和求区间最大值求区间最小值
简单介绍一下线段树
线段树是一个将区间内的数不断细分的一种数据结构#xff0c;也就是一个完全二叉树#xff0c;用每一…线段树是常用来维护 区间信息 的数据结构
线段树可以在 O(logN) 的时间复杂度内实现
单点修改区间修改区间查询 区间求和求区间最大值求区间最小值
简单介绍一下线段树
线段树是一个将区间内的数不断细分的一种数据结构也就是一个完全二叉树用每一个叶子节点代表一个区间内的值 操作1单点修改
单点修改是找到要修改的那个点所在的每一层的区间最后通过叶子节点修改为相应的值然后向上递归 操作2区间查询
区间查询[l,r]是指在线段树内从上向下查询如果子区间的左右端点都在[l,r]内则不用在向下递归直到找到所有的点 常用操作函数
pushup(int u)用子节点的信息更新当前节点 参数u是根节点
static void pushUp(int u){node[u].sumnode[u1].sumnode[u1|1].sum;
}
build(int u,int l,int r)在一段区间上初始化线段树 参数u是根节点l是区间左端点r是区间右端点
static void build(int u,int l,int r){if(lr)node[u]new Node(l,r,w[r]);else{node[u]new Node(l,r,0);int midlr1;build(u1,l,mid);build(u1|1,mid1,r);pushUp(u);}
}
modify(int u,int x,int v)修改某一点的值 参数u是根节点x是要修改的节点v是要增加或减小的值
static void modify(int u,int x,int v){if(node[u].lnode[u].r)node[u].sumv;else{int mid(node[u].lnode[u].r)1;if(xmid)modify(u1,x,v);else modify(u1|1,x,v);pushUp(u);}
}
query(int u,int l,int r)查询 参数u是根节点l是区间左端点r是区间右端点
static int query(int u,int l,int r){if(node[u].llnode[u].rr)return node[u].sum;int midnode[u].lnode[u].r1;int sum0;if(lmid)sumquery(u1,l,r);if(rmid)sumquery(u1|1,l,r);return sum;
}
节点表示
父节点x/2 x1
左儿子2x x1
右儿子2x1 x1|1 动态求连续区间和
package 线段树;import java.io.BufferedReader;
import java.io.InputStreamReader;public class Main {static int N1000010;static Node[] nodenew Node[N];static int[] wnew int[N];static BufferedReader brnew BufferedReader(new InputStreamReader(System.in));static int n,m;static String[] $;static void pushUp(int u){node[u].sumnode[u1].sumnode[u1|1].sum;}static void build(int u,int l,int r){if(lr)node[u]new Node(l,r,w[r]);else{node[u]new Node(l,r,0);int midlr1;build(u1,l,mid);build(u1|1,mid1,r);pushUp(u);}}static int query(int u,int l,int r){if(node[u].llnode[u].rr)return node[u].sum;int midnode[u].lnode[u].r1;int sum0;if(lmid)sumquery(u1,l,r);if(rmid)sumquery(u1|1,l,r);return sum;}static void modify(int u,int x,int v){if(node[u].lnode[u].r)node[u].sumv;else{int mid(node[u].lnode[u].r)1;if(xmid)modify(u1,x,v);else modify(u1|1,x,v);pushUp(u);}}public static void main(String[] args)throws Exception {$br.readLine().split( );nInteger.parseInt($[0]);mInteger.parseInt($[1]);$br.readLine().split( );for(int i1;in;i)w[i]Integer.parseInt($[i-1]);build(1,1,n);while (m--0){$br.readLine().split( );int kInteger.parseInt($[0]);int aInteger.parseInt($[1]);int bInteger.parseInt($[2]);if(k0)System.out.println(query(1,a,b));else modify(1,a,b);}}
}class Node{int l,r,sum;public Node(int l,int r,int sum){this.ll;this.rr;this.sumsum;}
}
