算法模板题记录
文章目录
- 前言
- 一、线段树
- 模板题
- 代码实现
前言
用于记录在算法学习过程中遇到典型的题目，方便日后个人查看。
一、线段树
模板题
LeetCode 307
代码实现
class NumArray {private int[] segmentTree ; private int n ; public NumArray(int[] nums) {n = nums.length ; segmentTree = new int[4*n] ; // 线段 区间值// 构建线段树build(1, 1, n, nums);}// 构建 线段树 private void build(int node, int s ,int e ,int[] nums) { // node 代表线段树的当前节点// [s,e] 代表当前线段树 维护的区间// nums 记录向线段树中要加入的值if(s == e) {segmentTree[node] = nums[s-1] ; return ; }int mid =s + (e-s) / 2 ;// 维护左子树build(2*node, s ,mid , nums);// 维护右子树build(2*node+1, mid+1 ,e , nums);// 维护当前节点 等于 左右子树的区间值之和segmentTree[node] = segmentTree[2*node]+segmentTree[2*node+1] ; }// 更新线段树 某个节点的值public void change(int node, int s, int e, int index, int val) {if(s == e) {segmentTree[node] = val; return ; }int mid =s + (e-s) / 2 ;// 根据index 进行查找，查找index 所在的区间if(index<=mid) { // 查找 左子树change(node*2, s, mid, index, val) ; }else { // 查找 又子树change(node*2+1, mid+1, e, index, val) ; }segmentTree[node] = segmentTree[2*node]+segmentTree[2*node+1] ; }// 根据范围查询区间值private int range(int node ,int s, int e ,int L, int R) {// 如果要查询的范围 包含当前节点所维护的范围，直接返回当前范围的值if(L<=s && R>=e) {return segmentTree[node] ; }int count = 0; // 依次遍历左右子树 来获得最终的子段和int mid = s+(e-s)/2; if(L<=mid) {count += range(2*node, s, mid, L, R); }if(R>mid) {count+= range(2*node+1, mid+1, e, L, R) ; }return count ; }public void update(int index, int val) {change(1, 1, n, index+1, val);}public int sumRange(int left, int right) {return range(1, 1, n, left+1, right+1) ; }
}