烟台百度网站推广,做网站工作室找客户难,区域销售网站什么做,中国互联网协会卢卫1. 题目
在类的构造函数中给一个整数数组, 实现两个方法 query(start, end) 和 modify(index, value):
对于 query(start, end), 返回数组中下标 start 到 end 的 和。对于 modify(index, value), 修改数组中下标为 index 上的数为 value.
样例1
输入:
[1,2,7,8,5]
[query(0…1. 题目
在类的构造函数中给一个整数数组, 实现两个方法 query(start, end) 和 modify(index, value):
对于 query(start, end), 返回数组中下标 start 到 end 的 和。对于 modify(index, value), 修改数组中下标为 index 上的数为 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]
说明:
给定数组 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] 修改为 1A [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挑战
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(vectorint 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,mid1,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 vlvr;}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(vectorint 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% 数据通过测试 总耗时: 1086ms
