使用线段树查询给定范围内偶数位数和元素的个数

---

引言

在本教程中，我们将使用 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

结论

我们已经完成了本教程。在这里，我们找到了一种方法来解决给定范围内偶数位数和元素计数的查询，方法是使用线段树。我们使用线段树实现了两种解决问题陈述的方法。本教程中使用的演示阐述了问题陈述的目的。