第一行有二個整數 $n, q$，表示數列 $a$ 中有幾個數以及有幾個詢問。
第二行有 $n$ 個整數，第 $i$ 個整數 $a_i$ 代表數列 $a$ 中的第 $i$ 個數為 $a_i$。
接下來有 $q$ 行，第 $i+2$ 行首先有一個整數 $qt_i$ ，表示問題的類型，接著根據不同的問題類型有不同的輸入：
若 $qt_i=1$ ，接下來有兩個整數 $k$ 和 $x$ ，表示要將數列 $a$ 的第 $k$ 項改為 $x$ 。
若 $qt_i=2$ ，接下來有兩個整數 $l$ 和 $r$ ，請輸出 $a[l] + a[l+1] + .... + a[r-1] + a[r]$ 。
若 $qt_i=3$ ，接下來有兩個整數 $l$ 和 $r$ ，請輸出 $a[l], a[l+1], ..., a[r-1], a[r]$ 之間的最大值 。

$\forall i$, $qt_i=2$ 或 $qt_i=3$ 輸出一行包含一個整數，表示該次詢問的答案。

基本介紹
相信大家多少都有聽過「線段樹」吧！
沒聽過的話也沒關係， 這裡有維基百科可以參考一下。
如果你懶得點那個連結，我們在這裡節錄一段（如果有勤奮的點開連結就可以略過這段）：
「線段樹是一種二元樹，可視為樹狀陣列的變種，最早出現在2001年，由演算法競賽選手發明。
線段樹是一種將陣列儲存為樹的資料結構。這允許高效地回答陣列上的範圍查詢，同時仍然足夠靈活以允許快速修改陣列。 這包括尋找連續陣列元素 $a[l \dots r]$ 的總和，或在 $O(\log n)$ 時間內找到此類範圍內的最小元素（範圍最值查詢）。在回答此類查詢之間，線段樹允許通過替換一個元素甚至更改整個子段的元素來修改陣列（例如，將所有元素 $a[l \dots r]$ 分配給任何值，或為子段中的所有元素增加一個值）。」

看完還不知道如何實作嗎？這就對了，接下來來教各位如何實作這題（之後的實作會使用到vector，參考）。
對了，為了避免大家不知道為什麼要學習線段樹，我們必須先來了解一下它有那些好處。
為什麼要學習並使用線段樹？
如果各位有認真閱讀前方敘述可知，線段樹能使每次的查詢和修改的複雜度從原本的 $O(n)$ 變為 $O(\log n)$ ，在本題中，詢問複雜度可從$O(n q)$變為$O(q \log n)$，換句話說，若使用線段樹，即可處理 $q \le 2 \times 10^{5}$ 的問題，而因本題 $q \le 10^{4}$ ，不須線段樹即可拿到滿分，若想練習可參考這題，若想繼續學習可以往下閱讀。
實作
輸入相信大家都會，就不贅述了。我們只講需要實作的三個函式：
1. build
我們要實作void build(vector<int> &tr,vector<int> &v,int l,int r,int now)，用來蓋線段樹。v是原本的陣列，tr是線段樹，[l, r]是tr[now]所管理的部分。在這個函式中，要有以下幾個部分：
1. 蓋到最下面時停止，處理目前節點資訊。
2. 如果要往下蓋的話，要把目前的區間切一半，蓋完左右子節點後再處理目前的節點。
2. modify
我們要實作void modify(vector<int> &tr,int l,int r,int k,int x,int now)，用來更改某些節點的值。tr是線段樹，[l, r]是tr[now]所管理的部分，目的是要將原陣列中第k項改成x。在這個函式中，要有以下幾個部分：
1. 走到最下面時停止，更改節點數值。
2. 如果要往下走的話，要把目前的區間切一半，改完左右子節點後再改動目前的節點。
3. query
我們要實作int query(vector<int> &tr,int l,int r,int ql,int qr,int now)，用來更改某些節點的值。tr是線段樹，[l, r]是tr[now]所管理的部分，[ql, qr]是要詢問的區間。在這個函式中，要有以下幾個部分：
1. 走到最下面時停止，回傳節點數值。
2. 如果要往下走的話，先將目前區間切半，之後要考慮三種情況：
1. 詢問區間全部在左邊，只走左邊。
2. 詢問區間全部在右邊，只走右邊。
3. 詢問區間覆蓋左右，把詢問區間也切半，兩邊都走，要記得合併完再回傳數值。
恭喜你實作完三個函式了！剩下的部分就只要根據詢問作處理就好了，是不是非常簡單呢？