在分段樹中查詢

Question

我一直在努力去理解query()函數中最後6行的邏輯。

這是spoj上問題GSS1的代碼。

解決方案link

#include <cstdio> 
#include <algorithm> 
#define MAX 70000 

using namespace std; 

struct no { 
int lsum, rsum, msum; 
}; 

int array[ MAX + 1 ], sums[ MAX + 1 ]; 
no tree[ 4 * MAX + 1 ]; 

void init(int node, int i, int j) { 
if (i == j) { 
    tree[ node ] = ((no) { array[ i ], array[ i ], array[ i ] }); 
} 
else { 
    init(node * 2, i, (i + j)/2); 
    init(node * 2 + 1, (i + j)/2 + 1, j); 
    no left = tree[ node * 2 ], right = tree[ node * 2 + 1 ]; 
    tree[ node ].lsum = max(left.lsum, sums[ (i + j)/2 ] - sums[ i - 1 ] + right.lsum); 
    tree[ node ].rsum = max(right.rsum, sums[ j ] - sums[ (i + j)/2 ] + left.rsum); 
    tree[ node ].msum = max(left.msum, max(right.msum, left.rsum + right.lsum)); 
}} 

no query(int node, int a, int b, int i, int j) { 
if (a == i && b == j) { 
    return tree[ node ]; 
} 
else if (j <= (a + b)/2) { 
    return query(node * 2, a, (a + b)/2, i, j); 
} 
if (i > (a + b)/2) { 
    return query(node * 2 + 1, (a + b)/2 + 1, b, i, j); 
} 
no left = query(node * 2, a, (a + b)/2, i, (a + b)/2); 
no right = query(node * 2 + 1, (a + b)/2 + 1, b, (a + b)/2 + 1, j); 
return ((no) { 
      max(left.lsum, sums[ (a + b)/2 ] - sums[ i - 1 ] + right.lsum), 
      max(right.rsum, sums[ b ] - sums[ (a + b)/2 ] + left.rsum), 
      max(left.msum, max(right.msum, left.rsum + right.lsum)) 
      }); } 

int main() { 
int i, N, q, l, r; 
scanf("%d", &N); 
for (i = 0; i < N; ++i) { 
    scanf("%d", array + i); 
    if (i == 0) { 
     sums[ i ] = array[ i ]; 
    } 
    else { 
     sums[ i ] = sums[ i - 1 ] + array[ i ]; 
    } 
} 
init(1, 0, N - 1); 
scanf("%d", &q); 
for (i = 0; i < q; ++i) { 
    scanf("%d%d", &l, &r); 
    --l; 
    --r; 
    printf("%d\n", query(1, 0, N - 1, l, r).msum); 
} 
return 0; } 

什麼是沒有=左邊的& &無=右的需要，查詢功能的回報。

任何人都應該提出更好的實現/教程fr段樹。

我無法在實現數據結構時看到這些遞歸。任何提示？

Answer 1

什麼是無=的需要留下& &無=右和 查詢功能

這就是你查詢到段進入兩個孩子的情況下返回。假設你有一個覆蓋區間1..n的節點，並且有2個孩子1 .. n/2和n/2 + 1 ..n。如果你想查詢一些間隔[a，b]，使得< = n/2 < b，那麼你需要從左分支和右分支獲得結果並將它們合併（換句話說，將查詢分成[a ，n/2]和[n/2 +1，b]得到2個結果併合並它們

爲了提高效率，您可以證明，因爲間隔現在觸摸的邊距（所以當你總是遍歷其中一個孩子時，另一個或者被忽略或者完全落入查詢內部，並且在下一個遞歸步驟中返回）

該代碼用於非常高效的實現不存儲指向兒童的指針，節點範圍是隱含的）。如果你正試圖學習/調試外觀用於更明確地存儲事物的東西，或者自己寫一個東西。至少要正確縮進代碼，將變量名稱更改爲更具可讀性，並用middle替換(a+b)/2。這應該使代碼更易於理解。也可以在紙上繪製結構（總是有幫助）。