秋名山碼民的主頁
🎉歡迎關(guān)注🔎點(diǎn)贊👍收藏??留言📝
🙏作者水平有限，如發(fā)現(xiàn)錯誤，還請私信或者評論區(qū)留言！

---

前言

線段樹算是比較難的一個數(shù)據(jù)結(jié)構(gòu)，當(dāng)時我高中提高組就沒學(xué)懂，細(xì)數(shù)我學(xué)線段樹也學(xué)了4遍，最早學(xué)的時候一臉懵逼，最近在刷題中發(fā)現(xiàn)其在藍(lán)橋杯中也有考察，就尋思寫一篇博客來鞏固。

什么是線段樹，線段樹有什么用，線段樹怎么寫，能不能背過？？？

我認(rèn)為對于打比賽的各位來說，線段樹和前綴和一樣，不能算做算法，它更多的是一種工具，一種時間復(fù)雜度為O(logn)的單點(diǎn)修改，區(qū)間查詢的工具

線段樹邏輯概念

給定一個1~7的區(qū)間我們來維護(hù)它，將其轉(zhuǎn)換為一個二叉樹（線段樹本身就是一個二叉樹）

1. 最上面的根的權(quán)值，為28，1~7的和
2. 二叉樹開分，左邊為1~4的和為10，右邊為5 ~ 6的和為21
3. 1~4在開分，左邊為3，右邊為7 ，5 ~6開分，左邊為14，右邊為7
4. 同上，直到不能再分

L，R：

class node{int l,r;int sum;
}

線段樹的倆個重要用處

1. 單點(diǎn)修改

如上圖我們將5變成8，其中要修改的為1~ 7，5~ 7，5~ 6，5，

2. 區(qū)間查詢

如上圖我們計算2 ~ 5區(qū)間，如果完全包含某個區(qū)間，則退出，否則進(jìn)行遞歸，用黃圈表示需要遞歸的區(qū)間

1. 1~7區(qū)間，遞歸左邊，1 ~4區(qū)間，發(fā)現(xiàn)還沒有被完全包含，進(jìn)行左右倆邊都遞歸，1 ~2，3 ~4，此刻，3 ~4完全包含，不進(jìn)行遞歸，繼續(xù)遞歸1~ 2，2被完全包含
2. 5~ 7區(qū)間，同上，進(jìn)行遞歸
3. 進(jìn)行回溯區(qū)間，只算完全包含的區(qū)間，2+7+8 = 17

總結(jié)：
如果這個區(qū)間被完全包括在目標(biāo)區(qū)間里面，直接返回這個區(qū)間的值
如果這個區(qū)間的左兒子和目標(biāo)區(qū)間有交集，那么搜索左兒子
如果這個區(qū)間的右兒子和目標(biāo)區(qū)間有交集，那么搜索右兒子

時間復(fù)雜度均為O(logn)

代碼實(shí)現(xiàn)線段樹

上面我們說線段樹的倆個重要的用法，思考一下大概需要幾個函數(shù)能實(shí)現(xiàn)？

1. pushup：用子節(jié)點(diǎn)信息更新當(dāng)前節(jié)點(diǎn)信息
2. build：在一段區(qū)間上初始化線段樹
3. modify：修改
4. query：查詢

動態(tài)求連續(xù)區(qū)間和

import java.io.*;/*** @Author 秋名山碼神* @Date 2023/2/9* @Description*/
public class 動態(tài)求連續(xù)區(qū)間和 {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 i=1;i<=n;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);}}
}

題目鞏固

區(qū)間和的個數(shù)

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];}Set<Long> set = new HashSet<Long>();for (int i = 0; i <= length; i++) {long sum = sums[i];set.add(sum);set.add(sum - upper);set.add(sum - lower);}List<Long> sumsList = new ArrayList<Long>(set);Collections.sort(sumsList);Map<Long, Integer> ranks = new HashMap<Long, 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];}
}

最后

看在博主這么努力，熬夜肝的情況下，給個免費(fèi)的三連吧！