国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

我理解的數據結構(八)—— 線段樹(SegmentTree)

shaonbean / 880人閱讀

摘要:示例解題代碼注意,如果要在上提交解答,必須把接口和類的代碼一并提交,這里并沒有在寫類中

我理解的數據結構(八)—— 線段樹(SegmentTree) 一、什么是線段樹

1.最經典的線段樹問題:區間染色
有一面墻,長度為n,每次選擇一段墻進行染色,m次操作后,我們可以看見多少種顏色?m次操作后,我們可以在[i, j]區間內看見多少種顏色?

數據結構 染色操作 查詢操作
數組 O(n) O(n)

2.其他應用場景
2017年注冊用戶中消費最高的用戶?消費最少的用戶?學習時間最長的用戶?

3.復雜度比較

數據結構 更新 查詢
數組 O(n) O(n)
線段樹 O(logn) O(logn)

4.線段樹原理圖
以求和為例:

二、線段樹基礎

1.基礎

線段樹不是完全二叉樹

線段樹是平衡二叉樹(整棵樹最大深度和最小深度最大差為1)

線段樹依然可以用數組表示

把不存在的節點看成null,線段樹即是完全二叉樹

2.數組存儲線段樹的空間需求

0層 1層 ... h-1層
1 2 ... 2^(h-1)

對滿二叉樹:

h層,一共有2^h-1個節點(大約2^h)

最后一層(h-1)層,有2^(h-1)個節點

最后一層的節點數大致等于前面所有層節點之和

如果需要存儲n個元素

n=2^k,只需要2n的空間

n=2^k+1,需要4n的空間

三、線段樹基礎代碼
public class SegmentTree {

    private E[] data;
    private E[] tree;

    public SegmentTree(E[] arr) {
        data = (E[])new Object[arr.length];

        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        tree = (E[])new Object[4 * arr.length];
    }

    // 獲取元素個數
    public int getSize() {
        return data.length;
    }

    // 獲取某個索引上的值
    private E get(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("index is illegal");
        }

        return data[index];
    }

    // 返回完全二叉樹的數組表示中,一個索引所表示的元素的左子樹的索引
    private int leftChild(int index) {
        return 2 * index + 1;
    }

    // 返回完全二叉樹的數組表示中,一個索引所表示的元素的右子樹的索引
    private int rightChild(int index) {
        return 2 * index + 2;
    }
}
四、創建線段樹代碼

1.定義融合器接口

public interface Merge {
    // 區間的元素如何定義由用戶決定
    E merge(E a, E b);
}

2.創建線段樹代碼

private Merge merge;

public SegmentTree(E[] arr, Merge merge) {

    // 線段樹的融合器,用于定義線段樹的區間元素到底如何存儲
    this.merge = merge;

    data = (E[])new Object[arr.length];

    for (int i = 0; i < arr.length; i++) {
        data[i] = arr[i];
    }
    tree = (E[])new Object[4 * arr.length];
    buildSegmentTree(0, 0, data.length - 1);
}

// 遞歸:在treeIndex的位置創建表示區間[l,r]的線段樹
private void buildSegmentTree(int treeIndex, int l, int r) {
    if (l == r) {
        tree[treeIndex] = data[l];
        return;
    }

    int leftTreeIndex = leftChild(treeIndex);
    int rightTreeIndex = rightChild(treeIndex);
    int min = (l + r) / 2;

    buildSegmentTree(leftTreeIndex, l, min);
    buildSegmentTree(rightTreeIndex, min + 1, r);
    tree[treeIndex] = merge.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}

@Override
public String toString() {

    StringBuilder res = new StringBuilder();

    res.append("[");
    for (int i = 0; i < tree.length; i++) {
        if (tree[i] == null) {
            res.append("null");
        } else {
            res.append(tree[i]);
        }

        if (i != tree.length - 1) {
            res.append(", ");
        }

    }
    res.append("]");

    return res.toString();
}
五、線段樹的查詢

// 線段樹的查詢操作,區間[queryL, queryR]
public E query(int queryL, int queryR) {

   if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length) {
       throw new IllegalArgumentException("queryL or queryR is illegal");
   }

   return query(0, 0, data.length - 1, queryL, queryR);
}

// 遞歸,以treeIndex為根節點,區間為[l, r],查詢區間為[queryL, queryR]
private E query(int treeIndex, int l, int r, int queryL, int queryR) {

   if (l == queryL && r == queryR) {
       return tree[treeIndex];
   }

   int leftChildIndex = leftChild(treeIndex);
   int rightChildIndex= rightChild(treeIndex);
   int mid = (l + r) / 2;

   if (queryL >= mid + 1) {
       return query(rightChildIndex, mid + 1, r, queryL, queryR);
   } else if (queryR <= mid) {
       return query(leftChildIndex, l, mid, queryL, queryR);
   }

   E left = query(leftChildIndex, l, mid, queryL, mid);
   E right = query(rightChildIndex, mid + 1, r, mid + 1, queryR);
   return merge.merge(left, right);
}
六、LeetCode上303號問題

題目:303. 區域和檢索 - 數組不可變
描述:給定一個整數數組 nums,求出數組從索引 i 到 j (i ≤ j) 范圍內元素的總和,包含 i, j 兩點。
示例:

給定 nums = [-2, 0, 3, -5, 2, -1],求和函數為 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

解題代碼:

// 注意,如果要在leetcode上提交解答,必須把Merge接口和SegmentTree類的代碼一并提交,這里并沒有在寫NumArray類中
public class NumArray {

    private SegmentTree segTree;

    public NumArray(int[] nums) {

        if (nums.length > 0) {

            Integer[] data = new Integer[nums.length];
            for (int i = 0; i < nums.length; i++) {
                data[i] = nums[i];
            }

            segTree = new SegmentTree<>(data, (a, b) -> a + b);
        }
    }

    public int sumRange(int i, int j) {
        if (segTree == null) {
                throw new IllegalArgumentException("segment tree is null");
        }
        return segTree.query(i, j);
    }

}
七、線段樹的更新
public void set(int index, E e) {

    if (index < 0 || index >= data.length) {
        throw new IllegalArgumentException("index is illegal");
    }

    set(0, 0, data.length - 1, index, e);
}

private void set(int treeIndex, int l, int r, int index, E e) {
    if (l == r) {
        tree[treeIndex] = e;
        return;
    }

    int leftChildIndex = leftChild(treeIndex);
    int rightChildIndex= rightChild(treeIndex);
    int mid = (l + r) / 2;

    if (index >= mid + 1) {
        set(rightChildIndex, mid + 1, r, index, e);
    } else if (index <= mid) {
        set(leftChildIndex, l, mid, index, e);
    }

    tree[treeIndex] = merge.merge(tree[leftChildIndex], tree[rightChildIndex]);
}
八、LeetCode上307號問題

題目:307. 區域和檢索 - 數組可修改
描述:給定一個整數數組 nums,求出數組從索引 i 到 j (i ≤ j) 范圍內元素的總和,包含 i, j 兩點。
示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

解題代碼:

class NumArray {

    // 注意,如果要在leetcode上提交解答,必須把Merge接口和SegmentTree類的代碼一并提交,這里并沒有在寫NumArray類中    
    private SegmentTree segTree;
    
    public NumArray(int[] nums) {
        if (nums.length > 0) {

            Integer[] data = new Integer[nums.length];
            for (int i = 0; i < nums.length; i++) {
                data[i] = nums[i];
            }

            segTree = new SegmentTree<>(data, (a, b) -> a + b);
        }
    }

    public void update(int i, int val) {
        if (segTree == null) {
            throw new IllegalArgumentException("segment tree is null");
        }
        segTree.set(i, val);
    }

    public int sumRange(int i, int j) {
        if (segTree == null) {
            throw new IllegalArgumentException("segment tree is null");
        }
        return segTree.query(i, j);
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/29618.html

相關文章

  • 理解數據結構)—— 線段SegmentTree

    摘要:示例解題代碼注意,如果要在上提交解答,必須把接口和類的代碼一并提交,這里并沒有在寫類中 我理解的數據結構(八)—— 線段樹(SegmentTree) 一、什么是線段樹 1.最經典的線段樹問題:區間染色有一面墻,長度為n,每次選擇一段墻進行染色,m次操作后,我們可以看見多少種顏色?m次操作后,我們可以在[i, j]區間內看見多少種顏色?showImg(https://segmentfau...

    waltr 評論0 收藏0
  • LuxTdmZtIC

    摘要:轉載史上最簡單的平衡樹無旋作者博客地址使用此文件時請保留上述信息謝謝合作覺得文章不錯請點擊鏈接為博客點贊高能預警所有示例代碼都是數組版的歡迎前置知識線段樹請確保你完全理解最基礎的線段樹和區間加法和區間求和一簡介無旋又稱是范浩強大佬發明的一種 【轉載】史上最簡單的平衡樹——無旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    CoffeX 評論0 收藏0
  • LuxTdmZtIC

    摘要:轉載史上最簡單的平衡樹無旋作者博客地址使用此文件時請保留上述信息謝謝合作覺得文章不錯請點擊鏈接為博客點贊高能預警所有示例代碼都是數組版的歡迎前置知識線段樹請確保你完全理解最基礎的線段樹和區間加法和區間求和一簡介無旋又稱是范浩強大佬發明的一種 【轉載】史上最簡單的平衡樹——無旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    tuantuan 評論0 收藏0
  • LuxTdmZtIC

    摘要:轉載史上最簡單的平衡樹無旋作者博客地址使用此文件時請保留上述信息謝謝合作覺得文章不錯請點擊鏈接為博客點贊高能預警所有示例代碼都是數組版的歡迎前置知識線段樹請確保你完全理解最基礎的線段樹和區間加法和區間求和一簡介無旋又稱是范浩強大佬發明的一種 【轉載】史上最簡單的平衡樹——無旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    roundstones 評論0 收藏0
  • 【轉載】史上最簡單平衡——無旋Treap

    摘要:轉載史上最簡單的平衡樹無旋作者博客地址使用此文件時請保留上述信息謝謝合作覺得文章不錯請點擊鏈接為博客點贊高能預警所有示例代碼都是數組版的歡迎前置知識線段樹請確保你完全理解最基礎的線段樹和區間加法和區間求和一簡介無旋又稱是范浩強大佬發明的一種 【轉載】史上最簡單的平衡樹——無旋Treap 作者:fzszkl 博客地址:https://ac.nowcoder.com/discu... ...

    崔曉明 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<