C++ 使用段树查询给定范围内偶数数字和元素的数量

在本教程中，我们使用C++实现了一种方法来解决查询给定范围内偶数数字和元素数量的问题。我们使用了段树。为了解决这个任务，我们考虑一个元素数组，查询定义了子数组的范围。在该子数组中计数偶数数字和元素。使用段树预定义元素数组和查询来解决这个问题。

什么是段树？

段树是一种二进制数据结构，用于存储数组间隔或段的信息。它有效地解决了范围或段查询问题。段树的每个节点表示数组的一个范围，叶节点表示数组元素。

段树的关键操作是更新和范围查询。

在本教程中，我们使用段树的概念来解决元素数组的查询。

示例1

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

输出

2

解释

在上面的输入数组中，起始索引为0。查询定义了输入数组的索引。通过考虑查询，修订后的子数组为{4, 5, 6, 7}。在这个子数组中，有2个偶数和数字，即4和6。

示例2

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

输出

1

解释：

在上述输入数组中，有6个元素，起始索引为0。查询从索引1到3开始。使用Queries修订的子数组为{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

结论

我们已经到达本教程的结尾。在这里，我们通过使用线段树找到了解决给定范围内偶数位数字和元素计数查询的方法。我们实现了两种使用线段树解决这个问题的方式。本教程中使用的演示详细阐述了问题陈述的目的。