# LeetCode Range Sum Query - Mutable

LeetCode Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:

```Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
```

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

```class NumArray {
private:
struct Node {
int start, end, sum;
Node *left, *right;
Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {};
};
Node *root;
Node* constructTree(vector<int> &nums, int start, int end) {
Node* node = new Node(start, end);
if (start == end) {
node->sum = nums[start];
return node;
}
int mid = start + (end - start) / 2;
node->left = constructTree(nums, start, mid);
node->right = constructTree(nums, mid + 1, end);
node->sum = node->left->sum + node->right->sum;
return node;
}
int sumRange(int i, int j, Node *root) {
if (root == NULL)return 0;
if (i == root->start&&j == root->end)return root->sum;
int mid = root->start + (root->end - root->start) / 2;
if (j <= mid)return sumRange(i, j, root->left);
else if (i > mid)return sumRange(i, j, root->right);
else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right);
}
void update(int i, int val, Node *root) {
if (root->start == root->end && root->start == i) {
root->sum = val;
return;
}
int mid = root->start + (root->end - root->start) / 2;
if (i <= mid)update(i, val, root->left);
else update(i, val, root->right);
root->sum = root->left->sum + root->right->sum;
}
public:
NumArray(vector<int> nums) {
root = NULL;
if (!nums.empty())root = constructTree(nums, 0, nums.size() - 1);
}
void update(int i, int val) {
if (root == NULL)return;
update(i, val, root);
}
int sumRange(int i, int j) {
if (root == NULL)return 0;
return sumRange(i, j, root);
}
};
```

# hihoCoder 1077-RMQ问题再临-线段树

hihoCoder 1077-RMQ问题再临-线段树
#1077 : RMQ问题再临-线段树

10
3655 5246 8991 5933 7474 7603 6098 6654 2414 884
6
0 4 9
0 2 10
1 4 7009
0 5 6
1 3 7949
1 3 1227

2414
884
7474

```typedef struct node//线段树节点
{
int l;//区间左端点
int r;//区间右端点
int minv;//区间最小值
};
```

```#include<iostream>
#include<cstdio>
using namespace std;
const int MAX_N=1e6+2;
int w[MAX_N];
int n,q;
typedef struct node//线段树节点
{
int l;//区间左端点
int r;//区间右端点
int minv;//区间最小值
};
node tree[2*MAX_N];
inline int get_min(int a,int b)
{
return a<b?a:b;
}
//创建树
void build(int l,int r,int pos)
{
tree[pos].l=l;
tree[pos].r=r;
if(l==r)
tree[pos].minv=w[l];
else
{
int mid=(l+r)/2;
build(l,mid,pos*2);
build(mid+1,r,pos*2+1);
tree[pos].minv=get_min(tree[pos*2].minv,tree[pos*2+1].minv);
}
}
//查询树
int query(int l,int r,int pos)
{
if(l==tree[pos].l&&r==tree[pos].r)
return tree[pos].minv;
int mid=(tree[pos].l+tree[pos].r)/2;
if(r<=mid)
return query(l,r,pos*2);
else if(l>mid)
return query(l,r,pos*2+1);
else
{
int left=query(l,mid,pos*2);
int right=query(mid+1,r,pos*2+1);
return get_min(left,right);
}
}
//更新树
void update(int pi,int wi,int pos)
{
if(tree[pos].l==tree[pos].r&&tree[pos].l==pi)
tree[pos].minv=wi;
else
{
int mid=(tree[pos].l+tree[pos].r)/2;
if(pi<=mid)
update(pi,wi,pos*2);
else
update(pi,wi,pos*2+1);
tree[pos].minv=get_min(tree[pos*2].minv,tree[pos*2+1].minv);
}
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
build(1,n,1);
scanf("%d",&q);
int p,l,r;
for(int i=0;i<q;i++)
{
scanf("%d%d%d",&p,&l,&r);
if(p==0)
printf("%d\n",query(l,r,1));
else
update(l,r,1);
}
return 0;
}
```

P.S.之前用cin、cout超时，改成scanf、printf就好了，懒得取消同步什么的，以后就打算一直用scanf、printf了。唉，从上一题到这一题，优化是无止境的啊~~

# hihoCoder 1070-RMQ问题再临

hihoCoder 1070-RMQ问题再临
#1070 : RMQ问题再临

10
618 5122 1923 8934 2518 6024 5406 1020 8291 2647
6
0 3 6
1 2 2009
0 2 2
0 2 10
1 1 5284
0 2 5

1923
2009
1020
1923

```#include<iostream>
using namespace std;
const int MAX_N=1e4+2;
int w[MAX_N];//每个商品重量
int n,m;
int seg_tree[MAX_N][MAX_N];//seg_tree[i][j]：起点为i，长度为j的区间的最小值
inline int get_min(int a,int b)
{
return a<b?a:b;
}
//深度优先遍历以构造线段树
void dfs(int left,int length)
{
if(length==1)
{
seg_tree[left][1]=w[left];
return;
}
dfs(left,length/2);
dfs(left+length/2,length-length/2);
seg_tree[left][length]=get_min(seg_tree[left][length/2],seg_tree[left+length/2][length-length/2]);//取最小值
}
//在区间[s_left,s_len]搜索区间[left,length]的最小值
int search_min(int s_left,int s_len,int left,int length)
{
if((s_left==left)&&(s_len==length))
return seg_tree[s_left][s_len];
if((left+length-1)<(s_left+s_len/2))//全在左半部分
{
return search_min(s_left,s_len/2,left,length);
}
else if(left>=(s_left+s_len/2))//全在右半部分
{
return search_min(s_left+s_len/2,s_len-s_len/2,left,length);
}
else//左右分开搜索
{
int left_len=s_left+s_len/2-left;
int right_len=length-left_len;
int min_left=search_min(s_left,s_len/2,left,left_len);
int min_right=search_min(s_left+s_len/2,s_len-s_len/2,s_left+s_len/2,right_len);
return get_min(min_left,min_right);
}
}
//从区间[s_left,s_len]开始更新下标pos的值为value
void update(int s_left,int s_len,int pos,int value)
{
if((s_left==pos)&&(s_len==1))
{
seg_tree[s_left][1]=value;
return ;
}
int mid=s_left+s_len/2;
if(pos<mid)
update(s_left,s_len/2,pos,value);
else
update(mid,s_len-s_len/2,pos,value);
seg_tree[s_left][s_len]=get_min(seg_tree[s_left][s_len/2],seg_tree[mid][s_len-s_len/2]);//更新父节点
}
int main()
{
//freopen("input.txt","r",stdin);
cin>>n;
for(int i=1;i<=n;i++)
cin>>w[i];
dfs(1,n);
cin>>m;
int p,l,r;
for(int i=0;i<m;i++)
{
cin>>p>>l>>r;
if(p==0)//查询
{
cout<<search_min(1,n,l,r-l+1)<<endl;
}
else//修改
{
update(1,n,l,r);
}
}
return 0;
}
```

# hihoCoder 1069-最近公共祖先·三

hihoCoder 1069-最近公共祖先·三
#1069 : 最近公共祖先·三

“那到底要怎么办呢？在等到10分钟，或者凑够一定数量的人两个条件满足一个时就进行运算？”小Ho想出了一个折衷的办法。
“哪有这么麻烦！别忘了和离线算法相对应的可是有一个叫做在线算法的东西呢！”小Hi笑道。

4
Sam Joey
Sam Micheal
3
Sam Sam
Micheal Kevin

Sam

DFS生成的数组B长度大概为边数的两倍，所以复杂度级别只是O(n)的。
DFS之后就把树转换为了数组B[]，因为使用RMQ-ST算法需要求某个区间的最小深度节点，所以在DFS的时候还需要记录每个节点的深度信息，而且还要记录每个节点最后访问的下标，这两点都不难，大家直接看代码即可。
RMQ-ST算法

```#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
const int MAX_N=100010;//最大人数
map<string,int> name_index;//名字转换为数字
vector<string> index_name(MAX_N);//数字转换为名字
int n,m,k;//k全部记录将树转换成数组tree[]是的下标，转换结束时k即为tree[]的长度
vector<vector<int> > f_s(MAX_N);//f_s[i]表示第i个父亲的所有孩子
int tree[2*MAX_N];//DFS将树转换为的数组
int depth[MAX_N];//每个点在树中的深度
int rmq[MAX_N][30];//区间深度最低值
int last_show[MAX_N];//某个元素最后出现在tree中的位置（下标）
//保存某个人的信息，并返回其下标
int store_name(string name)
{
map<string,int>::iterator it=name_index.find(name);
if(it==name_index.end())//还不存在
{
int curr_index=name_index.size();//用当前已有人数作为其下标，正好是递增的。
name_index.insert(make_pair(name,curr_index));
index_name[curr_index]=name;//记录
return curr_index;//返回下标
}
else
return it->second;//已经存在，直接返回
}
//深度遍历树
void DFS(int root,int deep)
{
tree[k++]=root;//进入即记录
depth[root]=deep;//记录深度
int sons=f_s[root].size();
for(int i=0;i<sons;i++)
{
DFS(f_s[root][i],deep+1);
tree[k++]=root;//每返回一次都要记录一次根节点
}
last_show[root]=k-1;//root节点最后出现的位置
}
//求a,b最小值
inline int get_min(int a,int b)
{
return a<b?a:b;
}
void init_rmq()
{
for(int j=0;j<k;j++)
//rmq[j][0]=depth[tree[j]];
rmq[j][0]=tree[j];//保存的是这个节点，而不是它的深度，方便最后输出
int q=floor(log((double)k)/log(2.0));
for(int i=1;i<=q;i++)
{
for(int j=k-1;j>=0;j--)
{
rmq[j][i]=rmq[j][i-1];
if(j+(1<<(i-1))<k)
{
if(depth[rmq[j+(1<<(i-1))][i-1]]<depth[rmq[j][i]])//+优先级高于<<，所以改j+1<<(i-1)为j+(1<<(i-1))
rmq[j][i]=rmq[j+(1<<(i-1))][i-1];
}
//rmq[j][i]=get_min(rmq[j][i],rmq[j+1<<(i-1)][i-1]);
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
cin>>n;
string name1,name2;
int index1,index2;
while(n--)
{
cin>>name1>>name2;
index1=store_name(name1);
index2=store_name(name2);
f_s[index1].push_back(index2);
}
k=0;//开始时树的下标为0，DFS完之后正好是tree[]数组的长度，可以作为rmq-st的n
DFS(0,0);
init_rmq();
cin>>m;
int l,r,t;
while(m--)
{
cin>>name1>>name2;
if(name1==name2)
{
cout<<name1<<endl;
continue;
}
index1=store_name(name1);
index2=store_name(name2);
l=last_show[index1];
r=last_show[index2];
if(l>r)//保证l<=r
{
int tmp=r;
r=l;
l=tmp;
}
t=floor(log(double(r-l+1))/log(2.0));//找到能使[l,r]分为两半的指数
cout<<index_name[get_min(rmq[l][t],rmq[r-(1<<t)+1][t])]<<endl;//r-(1<<t)+1，记得+1
}
return 0;
}
```

# hihoCoder 1068-RMQ-ST算法

hihoCoder 1068-RMQ-ST算法
#1068 : RMQ-ST算法

（虽然说每次给出的区间仍然要小Hi来进行决定——但是小Hi最终机智的选择了使用随机数生成这些区间！但是为什么小Hi不直接使用随机数生成购物清单呢？——问那么多做什么！）

10
7334
1556
8286
1640
2699
4807
8068
981
4120
2179
5
3 4
2 8
2 4
6 8
7 10

1640
981
1556
981
981

RMQ-ST算法的基本思想是先计算某个小区间a的最小值，当需要计算大区间b的最小值时，把它分成两个小区间a1,a2，因为小区间的最小值之前已经计算出来了，也就是a1,a2已知，则b=min{a1,a2}。这样每次询问[l,r]区间的最小值时，我们也只需要把[l,r]分成两个[l,t]和[t+1,r]区间，取这两个区间最小值的最小值，这样的时间复杂度是O(1)。

```#include<stdio.h>
#include<math.h>
#define MAX_N 1000010
int n,q;
int weight[MAX_N];
int pre_calc[MAX_N][30];
//求a,b最小值
int get_min(int a,int b)
{
return a<b?a:b;
}
//初始化
void init_pre()
{
for(int j=1;j<=n;j++)
pre_calc[j][0]=weight[j];
int m=floor(log((double)n)/log(2.0));//指数最大值
for(int i=1;i<=m;i++)
{
for(int j=n;j>0;j--)
{
pre_calc[j][i]=pre_calc[j][i-1];
if(j+(1<<(i-1))<=n)//如果另一半也存在的话。//1<<(i-1)其实就是2^(i-1)
pre_calc[j][i]=get_min(pre_calc[j][i],pre_calc[j+(1<<(i-1))][i-1]);
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&weight[i]);
init_pre();
scanf("%d",&q);
int l,r,t;
while(q--)
{
scanf("%d%d",&l,&r);
t=floor(log(double(r-l+1))/log(2.0));//找到能使[l,r]分为两半的指数
printf("%d\n",get_min(pre_calc[l][t],pre_calc[r-(1<<t)+1][t]));
}
return 0;
}
```