使用線段樹查詢給定範圍內偶數位數和元素的個數

---

引言

在本教程中，我們將使用 C++ 實現一種方法來解決給定範圍內偶數位數和元素計數的查詢。我們將使用線段樹。為了解決此任務，我們考慮一個包含元素的陣列，查詢定義子陣列的範圍。在該子陣列中，計算偶數位數和元素的個數。預定義元素陣列和查詢，以便使用線段樹解決問題。

什麼是線段樹？

線段樹是一種二叉資料結構，用於儲存陣列區間或段資訊。它可以有效地解決範圍或段查詢問題。線段樹的每個節點都表示陣列的一個範圍，葉子節點表示陣列元素。

線段樹的關鍵操作是更新和範圍查詢。

在本教程中，我們將使用線段樹的概念來解決元素陣列的查詢。

演示1

Array = {1, 3, 4, 5, 6, 7, 8, 9}
Queries = [2, 5]

輸出

2

解釋

在上面的輸入陣列中，起始索引為 0。查詢定義輸入陣列索引。透過考慮查詢，修改後的子陣列為 {4, 5, 6, 7}。在這個子陣列中，有兩個偶數位數和元素，4 和 6。

演示2

Array = {2, 8, 1, 5, 6, 7}
Queries = [1,3]

輸出

1

解釋

在上面的輸入陣列中，有 6 個元素，起始索引號為 0。查詢從索引 1 到 3 開始。使用查詢修改後的子陣列為 {8, 1, 5}。在這個子陣列中，有一個偶數位數和元素 8。

C++ 庫函式

語法

vector: vector 是 C++ 中的一種動態陣列，它不限制陣列大小。使用它可以有效地插入和刪除陣列元素。它在 C++ 庫的 vector 標頭檔案中定義。

vector<data_type> vector_name;

sizeof(): 它是 C++ 中的一種一元運算子。它有助於在編譯時計算變數、常量和資料型別的大小。

sizeof(variable_name);

size(): 它是 C++ 的標準庫函式。它返回輸入字串的大小。

string_name.size();

演算法

• 考慮一個輸入陣列 arr[] 並定義其元素。

• 使用此陣列構建線段樹。

• 每個陣列元素都表示線段樹的葉子節點。

• 要構建線段樹，從兩個陣列元素開始，將樹分成兩部分。現在取第三個陣列元素，並根據線段樹插入規則將其插入。類似地，插入所有陣列元素。

• 透過遍歷樹來計算偶數位數和元素的個數。

• 初始化一個計數器變數，並在找到偶數位數和元素時增加其計數。

• 列印計數器變數的結果。

示例1

在這裡，我們使用 C++ 實現此任務。定義一個“constructSegmentTree”函式，使用 arr[] 元素構建線段樹。使用 rangeBegin 和 RangeFinish 變數初始化查詢，函式“querySegTree”根據查詢計算結果。

#include <iostream>
#include <vector>

using namespace std;

// Constructing the Segment tree node using structure
struct Node{
    int cnt;  // counter variable to count even digit sum elments
};

// Function to initialize the segment tree
void constructSegmentTree(const vector<int>& arr, vector<Node>& segtree, int node, int begin, int finish) {
    if (begin == finish) {
        // Leaf node
        segtree[node].cnt = (arr[begin] % 2 == 0) ? 1 : 0;
    } else {
        int between = (begin + finish) / 2;
        int lChild = 2 * node + 1;
        int rChild = 2 * node + 2;

        // Building substrees
        constructSegmentTree(arr, segtree, lChild, begin, between);
        constructSegmentTree(arr, segtree, rChild, between + 1, finish);

        // Combine results of left and right subtrees
        segtree[node].cnt = segtree[lChild].cnt + segtree[rChild].cnt;
    }
}

// query resolution function  
int querySegTree(const vector<Node>& segtree, int node, int begin, int finish, int rangeBegin, int rangeFinish) {
    if (begin > rangeFinish || finish < rangeBegin)
        return 0;

    if (rangeBegin <= begin && rangeFinish >= finish)
        return segtree[node].cnt;

    int between = (begin + finish) / 2;
    int lChild = 2 * node + 1;
    int rChild = 2 * node + 2;

    int lResult = querySegTree(segtree, lChild, begin, between, rangeBegin, rangeFinish);
    int rResult = querySegTree(segtree, rChild, between + 1, finish, rangeBegin, rangeFinish);

    return lResult + rResult;
}

// code controller
int main(){
    // vector array
    vector<int> arr = {2, 5, 3, 7, 6, 8, 1};
    int s = arr.size();

    vector<Node> segtree(4 * s); //defining the segment tree
    constructSegmentTree(arr, segtree, 0, 0, s - 1);

//queries
    int rangeBegin = 1;
    int rangeFinish = 4;
    int counter = querySegTree(segtree, 0, 0, s - 1, rangeBegin, rangeFinish);

    cout << "Count of elements with even digit sum in the range [" << rangeBegin << ", " << rangeFinish << "]: "<< counter << endl;

    return 0;
}

輸出

Count of elements with even digit sum in the range [1, 4] : 1

示例2

在這裡，我們使用 C++ 實現此任務。使用所有元素初始化一個數組。預定義的查詢表示陣列的索引。使用陣列元素和使用者定義的函式構造線段樹，並計算偶數位數和元素的個數。

#include <bits/stdc++.h>
using namespace std;
 
int evenSumDigit(int n){
    int addition = 0;
    while (n){
        addition += (n % 10);
        n /= 10;
    }
 
    return addition;
}
 
// building the Segment Tree
void constructSegmentTree(vector<int>& segtree, int* a, int indexNo, int t, int f){
 
 //tree leaf node
    if (t == f){
        if (evenSumDigit(a[t]) & 1)
            segtree[indexNo] = 0;
        else
            segtree[indexNo] = 1;
        return;
    }
 
    int between = (t + f) / 2;
    constructSegmentTree(segtree, a, 2 * indexNo, t, between);
    constructSegmentTree(segtree, a, 2 * indexNo + 1,between + 1, f);
 
    segtree[indexNo] = segtree[2 * indexNo] + segtree[2 * indexNo + 1];
}
 
// processing queries
int queryArr(vector<int> segtree, int indexNo,int t, int f, int m, int q){

    if (q < t || m > f)
        return 0;
 
    if (t >= m && f <= q){
        return segtree[indexNo];
    }

    int between = (t + f) / 2;
    return (queryArr(segtree, 2 * indexNo, t, between, m, q) + queryArr(segtree, 2 * indexNo + 1,
                    between + 1, f, m, q));
}
 
// code controller
int main(){
    int a[] = { 7, 3, 19, 13, 5, 4 };
    int s = sizeof(a) / sizeof(a[0]);
    vector<int> segtree(4 * s + 1);
 
    int M = 2, S = 6;
 
    constructSegmentTree(segtree, a, 1, 0, s - 1);
 
    cout << "Number of even digit sum elements are: "<< queryArr(segtree, 1, 0, s - 1, M, S)
         << endl;
    return 0;
}

輸出

Number of even digit sum elements are: 3

結論

我們已經完成了本教程。在這裡，我們找到了一種方法來解決給定範圍內偶數位數和元素計數的查詢，方法是使用線段樹。我們使用線段樹實現了兩種解決問題陳述的方法。本教程中使用的演示闡述了問題陳述的目的。