杭州市住房和城乡建设厅网站,网页开发哪家好,宁波公司排名,购物网站的后台秋名山码民的主页 #x1f389;欢迎关注#x1f50e;点赞#x1f44d;收藏⭐️留言#x1f4dd; #x1f64f;作者水平有限#xff0c;如发现错误#xff0c;还请私信或者评论区留言#xff01; 目录前言线段树逻辑概念线段树的俩个重要用处代码实现线段树题目巩固最后… 秋名山码民的主页 欢迎关注点赞收藏⭐️留言 作者水平有限如发现错误还请私信或者评论区留言 目录前言线段树逻辑概念线段树的俩个重要用处代码实现线段树题目巩固最后前言
线段树算是比较难的一个数据结构当时我高中提高组就没学懂细数我学线段树也学了4遍最早学的时候一脸懵逼最近在刷题中发现其在蓝桥杯中也有考察就寻思写一篇博客来巩固。
什么是线段树线段树有什么用线段树怎么写能不能背过
我认为对于打比赛的各位来说线段树和前缀和一样不能算做算法它更多的是一种工具一种时间复杂度为O(logn)的单点修改区间查询的工具
线段树逻辑概念
给定一个1~7的区间我们来维护它将其转换为一个二叉树线段树本身就是一个二叉树
最上面的根的权值为281~7的和二叉树开分左边为1~4的和为10右边为5 ~ 6的和为211~4在开分左边为3右边为7 5 ~6开分左边为14右边为7同上直到不能再分
LR
class node{int l,r;int sum;
}线段树的俩个重要用处 1. 单点修改
如上图我们将5变成8其中要修改的为1~ 75~ 75~ 65 2. 区间查询
如上图我们计算2 ~ 5区间如果完全包含某个区间则退出否则进行递归用黄圈表示需要递归的区间
1~7区间递归左边1 ~4区间发现还没有被完全包含进行左右俩边都递归1 ~23 ~4此刻3 ~4完全包含不进行递归继续递归1~ 22被完全包含5~ 7区间同上进行递归进行回溯区间只算完全包含的区间278 17 总结 如果这个区间被完全包括在目标区间里面直接返回这个区间的值 如果这个区间的左儿子和目标区间有交集那么搜索左儿子 如果这个区间的右儿子和目标区间有交集那么搜索右儿子 时间复杂度均为O(logn)
代码实现线段树
上面我们说线段树的俩个重要的用法思考一下大概需要几个函数能实现
pushup用子节点信息更新当前节点信息build在一段区间上初始化线段树modify修改query查询
动态求连续区间和
import java.io.*;/*** Author 秋名山码神* Date 2023/2/9* Description*/
public class 动态求连续区间和 {static int n, k;static int[] a new int[100100];static Node[] tr new Node[400400];static class Node{int l, r, sum;Node(int l, int r, int sum) {this.l l;this.r r;this.sum sum;}}public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw new BufferedWriter(new OutputStreamWriter(System.out));String[] cd br.readLine().split( );n Integer.parseInt(cd[0]);k Integer.parseInt(cd[1]);String[] line br.readLine().split( );for (int i1;in;i)a[i] Integer.parseInt(line[i-1]);build(1, 1, n);while (k-- 0) {String[] li br.readLine().split( );int k Integer.parseInt(li[0]), l Integer.parseInt(li[1]), r Integer.parseInt(li[2]);if(k 0) {bw.write(String.valueOf(query(1, l, r)));bw.write(\n);} elsemodify(1, l, r);}bw.flush();}static void pushUp(int u) {tr[u].sum tr[u 1].sum tr[u 1 | 1].sum;}static void build(int u, int l, int r) {if(l r) tr[u] new Node(l , r, a[l]);else {tr[u] new Node(l ,r, 0);int mid l r 1;build(u 1, l, mid); build(u 1 | 1, mid 1, r);pushUp(u);}}static int query(int u, int l, int r) {if(tr[u].l l tr[u].r r) return tr[u].sum;int mid tr[u].l tr[u].r 1, sum 0;if(l mid) sum query(u 1, l, r);if(r mid) sum query(u 1 | 1, l , r);return sum;}static void modify(int u, int x, int v) {if(tr[u].l tr[u].r) tr[u].sum v;else {int mid tr[u].l tr[u].r 1;if(x mid) modify(u 1, x , v);else modify(u 1 | 1, x, v);pushUp(u);}}
}
题目巩固
区间和的个数 class Solution {public int countRangeSum(int[] nums, int lower, int upper) {int count 0;int length nums.length;long[] sums new long[length 1];for (int i 0; i length; i) {sums[i 1] sums[i] nums[i];}SetLong set new HashSetLong();for (int i 0; i length; i) {long sum sums[i];set.add(sum);set.add(sum - upper);set.add(sum - lower);}ListLong sumsList new ArrayListLong(set);Collections.sort(sumsList);MapLong, Integer ranks new HashMapLong, Integer();int size sumsList.size();for (int i 0; i size; i) {ranks.put(sumsList.get(i), i);}SegmentTree st new SegmentTree(size);for (int i 0; i length; i) {long sum sums[i];int rank ranks.get(sum);long minSum sum - upper, maxSum sum - lower;int start ranks.get(minSum), end ranks.get(maxSum);count st.getCount(start, end);st.add(rank);}return count;}
}class SegmentTree {int length;int[] tree;public SegmentTree(int length) {this.length length;this.tree new int[length * 4];}public int getCount(int start, int end) {return getCount(start, end, 0, 0, length - 1);}public void add(int rank) {add(rank, 0, 0, length - 1);}private int getCount(int rangeStart, int rangeEnd, int index, int treeStart, int treeEnd) {if (rangeStart rangeEnd) {return 0;}if (rangeStart treeStart rangeEnd treeEnd) {return tree[index];}int mid treeStart (treeEnd - treeStart) / 2;if (rangeEnd mid) {return getCount(rangeStart, rangeEnd, index * 2 1, treeStart, mid);} else if (rangeStart mid) {return getCount(rangeStart, rangeEnd, index * 2 2, mid 1, treeEnd);} else {return getCount(rangeStart, mid, index * 2 1, treeStart, mid) getCount(mid 1, rangeEnd, index * 2 2, mid 1, treeEnd);}}private void add(int rank, int index, int start, int end) {if (start end) {tree[index];return;}int mid start (end - start) / 2;if (rank mid) {add(rank, index * 2 1, start, mid);} else {add(rank, index * 2 2, mid 1, end);}tree[index] tree[index * 2 1] tree[index * 2 2];}
}最后
看在博主这么努力熬夜肝的情况下给个免费的三连吧
