1. 題目

在類的構(gòu)造函數(shù)中給一個整數(shù)數(shù)組, 實現(xiàn)兩個方法 query(start, end) 和 modify(index, value):

• 對于 query(start, end), 返回數(shù)組中下標 start 到 end 的 和。
• 對于 modify(index, value), 修改數(shù)組中下標為 index 上的數(shù)為 value.

樣例1 輸入: [1,2,7,8,5] [query(0,2),modify(0,4),query(0,1),modify(2,1),query(2,4)] 輸出: [10,6,14] 說明: 給定數(shù)組 A = [1,2,7,8,5]. 在query(0, 2)后, 1 + 2 + 7 = 10, 在modify(0, 4)后, 將 A[0] 修改為 4， A = [4,2,7,8,5]. 在query(0, 1)后, 4 + 2 = 6. 在modify(2, 1)后, 將 A[2] 修改為 1，A = [4,2,1,8,5]. After query(2, 4), 1 + 8 + 5 = 14.樣例2 輸入: [1,2,3,4,5] [query(0,0),query(1,2),quert(3,4)] 輸出: [1,5,9] 說明: 1 = 1 2 + 3 = 5 4 + 5 = 9挑戰(zhàn) query 和 modify 的時間復雜度需要為O(logN).

2. 解題

• 參考 線段樹 Segment Tree

class node { public:int sum;int start, end;node *left, *right;node(int s, int e, int v):start(s),end(e),sum(v){left = right = NULL;}static node* build(vector<int>& A, int l, int r){if(l > r)return NULL;node* head = new node(l,r,A[l]);if(l == r)return head;int mid = l+((r-l)>>1);head->left = build(A,l,mid);head->right = build(A,mid+1,r);head->sum = 0;if(head->left)head->sum += head->left->sum;if(head->right)head->sum += head->right->sum;return head;}static long long query(node* head, int s, int e){if(s > head->end || e < head->start)return 0;if(head->start >= s && head->end <= e)return head->sum;int vl = query(head->left, s, e);int vr = query(head->right,s, e);return vl+vr;}static void modify(node* head, int id, int val){if(head->start == head->end){head->sum = val;return;}int mid = (head->start + head->end)/2;if(id > mid)modify(head->right, id, val);elsemodify(head->left, id, val);head->sum = 0;if(head->left)head->sum += head->left->sum;if(head->right)head->sum += head->right->sum;} }; class Solution {node *head; public:Solution(vector<int> A) {head = node::build(A,0,A.size()-1);}long long query(int start, int end) {return node::query(head, start,end);}void modify(int index, int value) {node::modify(head, index,value);} };

100% 數(shù)據(jù)通過測試
總耗時: 1086ms

總結(jié)

以上是生活随笔為你收集整理的LintCode 207. 区间求和 II（线段树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。