如何設計一個資料結構

引言

這幾天，刷題碰到了好多需要自己設計資料結構的題目，優化存儲，提升方法效率，主要是通路和修改

比如，字元串的查找用字典樹，TrieNode，節點樹，每個char都是一個leaf。

很多時候，我們常用vector,queue,stack,map,set

使用不需要排序的map,set,使用unordered_map, unordered_set, 前者内部機制紅黑樹，後者hash

這是我們在教材裡面能夠學到的，驚歎于這些容器裡面的構造精美，抽象的疊代器iterator，在疊代器基礎上的使用的算法algorithm，為了增強适用性設計的擴充卡等等

但是，如果給我們一個需求，讓我們自己設計這樣的資料結構，怎麼辦？

舉例

class NumArray {
public:
    NumArray(vector<int> &nums) {  

    }

    void update(int i, int val) {

    }

    int sumRange(int i, int j) {

    }
};
           

隻有兩種操作，updata修改index=i的val,sumRange區間[i,j]求和,且假設這兩種操作是均勻分布的。