爲什麼在這個範圍內最小查詢代碼？

我試圖解決，只是涉及範圍最小Query.The環節的實施問題的一個很基本的問題是爲什麼在這個範圍內最小查詢代碼？

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/

但我超過了時間限制。請有人幫忙調試我的代碼。

#include <bits/stdc++.h> 
#define inf 1000000000000000000 
using namespace std; 

vector<long long> segTree(2000005 , 0); 
void createTree(vector<long long> v); 
void createTreeUtil(vector<long long> v , int s,int e , int pos); 
void updateTree(int x , int value , int n); 
void updateTreeUtil(int s , int e , int pos , int x , int value); 
long long getMinUtil(int s , int e , int pos , int srange , int erange); 

long long getMin(int s , int e , int n); 
int main(){ 
    int n,q; 
    cin >> n >> q; 

    vector<long long> v(n); 
    for(int i=0;i<n;++i) cin >> v[i]; 
    //cout << "yes" << endl; 
    createTree(v); 
    /*cout << "seg tree is " ; 
    for(int i=0;i<segTree.size();++i) cout << segTree[i] << " "; 
    cout << endl;*/ 
    //cout << "yes" << endl; 
    while(q--){ 
     int x , y; 
     char c; 
     cin >> c >> x >> y; 
     if(c == 'u'){ 
      --x; 
      updateTree(x , y , n); 
     } 
     else{ 
      --x , --y; 
      cout << getMin(x , y , n) << endl; 
     } 
    } 


    return 0; 
} 

void createTree(vector<long long> v){ 

    int l = v.size(); 
    createTreeUtil(v , 0 , l-1 , 0); 
} 

void createTreeUtil(vector<long long> v , int s,int e , int pos){ 
    if(s>e) return; 
    int left = 2*pos+1 , right = 2*pos+2; 
    if(s==e){ 
     segTree[pos] = v[s]; 
     return; 
    } 
    int mid = (s+e)/2; 
    createTreeUtil(v , s , mid , left); 
    createTreeUtil(v , mid+1 , e , right); 
    segTree[pos] = min(segTree[left] , segTree[right]); 

} 

void updateTree(int x , int value , int n){ 

    updateTreeUtil(0 , n-1 , 0 , x , value); 

} 

void updateTreeUtil(int s , int e , int pos , int x , int value){ 
    if(s == e){ 

     if(s == x) segTree[s] = value; 
     return; 
    } 
    if(x<s || x>e) return; 
    int left = 2*pos+1 , right= 2*pos+2 , mid = (s+e)/2; 
    updateTreeUtil(s , mid , left , x , value); 
    updateTreeUtil(mid+1 , e , right , x , value); 
    segTree[pos] = min(segTree[left] , segTree[right]); 
} 

long long getMin(int s , int e , int n){ 

    return getMinUtil(0 , n-1 , 0 , s , e); 

} 

long long getMinUtil(int s , int e , int pos , int srange , int erange){ 
    int mid = (s+e)/2 , left = 2*pos+1 , right = 2*pos+2; 
    if(s > erange || e < srange) return inf; 
    if(s >= srange && e <= erange) return segTree[pos]; 
    return min(getMinUtil(s , mid , left , srange , erange) ,    getMinUtil(mid+1 , e , right , srange , erange)); 
}

預先感謝

來源

2017-08-04 Gaurav Jha

時間限制被超過，因爲C++通過值傳遞參數。

這意味着每次調用createTreeUtil時，都會使用100,000個元素創建輸入向量的全新副本。

嘗試改變：

void createTree(vector<long long> v); 
void createTreeUtil(vector<long long> v , int s,int e , int pos);

使用引用：

void createTree(vector<long long> &v); 
void createTreeUtil(vector<long long> &v , int s,int e , int pos);

（您需要在其中函數聲明的文件的頂部，以改變這些特徵都和其中函數實際上是定義的。）

來源

2017-08-04 08:32:16

感謝您的幫助。但現在它顯示錯誤的答案。我認爲我在邏輯上也犯了一些錯誤。 –

爲什麼在這個範圍內最小查詢代碼？

回答

相關問題