work2/task45.cpp - develop - novd7/algirithms_sem2

work2/task45.cpp
175 строк6 KB
Новиков Владимир
work 2
03 апр 2026, 22:39
03 апр 2026, 22:3904518aa
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

struct Node {
    int l, r;
    Node* left;
    Node* right;
    int max_value, min_value;
    int sum;
    int odd_count, even_count;

    Node(int l, int r, int val) : l(l), r(r), left(nullptr), right(nullptr) {
        max_value = val;
        min_value = val;
        sum = val;
        odd_count = val % 2 != 0;
        even_count = val % 2 == 0;
    }

    Node(int l, int r, Node* left, Node* right) : l(l), r(r), left(left), right(right) {
        max_value = max(left->max_value, right->max_value);
        min_value = min(left->min_value, right->min_value);
        sum = left->sum + right->sum;
        odd_count = left->odd_count + right->odd_count;
        even_count = left->even_count + right->even_count;
    }
};

Node* buildTree(const vector<int>& arr, int l, int r) {
    if (l == r) return new Node(l, r, arr[l]);
    int mid = (l + r) / 2;
    Node* leftChild = buildTree(arr, l, mid);
    Node* rightChild = buildTree(arr, mid + 1, r);
    return new Node(l, r, leftChild, rightChild);
}

int queryMax(Node* node, int ql, int qr) {
    if (!node || qr < node->l || node->r < ql) return -1e9;
    if (ql <= node->l && node->r <= qr) return node->max_value;
    return max(queryMax(node->left, ql, qr), queryMax(node->right, ql, qr));
}

int queryMin(Node* node, int ql, int qr) {
    if (!node || qr < node->l || node->r < ql) return 1e9;
    if (ql <= node->l && node->r <= qr) return node->min_value;
    return min(queryMin(node->left, ql, qr), queryMin(node->right, ql, qr));
}

int querySum(Node* node, int ql, int qr) {
    if (!node || qr < node->l || node->r < ql) return 0;
    if (ql <= node->l && node->r <= qr) return node->sum;
    return querySum(node->left, ql, qr) + querySum(node->right, ql, qr);
}

int queryOdd(Node* node, int ql, int qr) {
    if (!node || qr < node->l || node->r < ql) return 0;
    if (ql <= node->l && node->r <= qr) return node->odd_count;
    return queryOdd(node->left, ql, qr) + queryOdd(node->right, ql, qr);
}

int queryEven(Node* node, int ql, int qr) {
    if (!node || qr < node->l || node->r < ql) return 0;
    if (ql <= node->l && node->r <= qr) return node->even_count;
    return queryEven(node->left, ql, qr) + queryEven(node->right, ql, qr);
}

void update(Node* node, int index, int newVal) {
    if (node->l == node->r) {
        node->max_value = newVal;
        node->min_value = newVal;
        node->sum = newVal;
        node->odd_count = (newVal % 2 != 0) ? 1 : 0;
        node->even_count = (newVal % 2 == 0) ? 1 : 0;
        return;
    }

    int mid = (node->l + node->r) / 2;
    if (index <= mid)
        update(node->left, index, newVal);
    else
        update(node->right, index, newVal);

    node->max_value = max(node->left->max_value, node->right->max_value);
    node->min_value = min(node->left->min_value, node->right->min_value);
    node->sum = node->left->sum + node->right->sum;
    node->odd_count = node->left->odd_count + node->right->odd_count;
    node->even_count = node->left->even_count + node->right->even_count;
}

void deleteTree(Node* node) {
    if (!node) return;
    deleteTree(node->left);
    deleteTree(node->right);
    delete node;
}

void printTree(Node* node, int depth = 0) {
    if (!node) return;

    for (int i = 0; i < depth; i++) cout << "  ";

    if (node->l == node->r) {
        cout << "ЛИСТ [" << node->l << "," << node->r << "] ";
    } else {
        cout << "УЗЕЛ [" << node->l << "," << node->r << "] ";
    }

    cout << "max=" << node->max_value << " min=" << node->min_value << " sum=" << node->sum
         << " odd=" << node->odd_count << " even=" << node->even_count << endl;

    printTree(node->left, depth + 1);
    printTree(node->right, depth + 1);
}

int main() {
    string line;
    cout << "Введите любое количество чисел через пробел: ";
    getline(cin, line);

    stringstream ss(line);
    vector<int> arr;
    int x;

    while (ss >> x) {
        arr.push_back(x);
    }

    if (arr.empty()) {
        cout << "Ошибка: массив пуст. Завершение программы." << endl;
        return 1;
    }

    int n = arr.size();
    cout << "\nВведено чисел: " << n << endl;
    cout << "📋 Массив: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i];
        if (i < n - 1) cout << ", ";
    }
    cout << endl;

    Node* root = buildTree(arr, 0, n - 1);

    cout << "\nСТРУКТУРА ДЕРЕВА ОТРЕЗКОВ:\n";
    cout << "================================\n";
    printTree(root);
    cout << "================================\n";
    cout << "\nКоличество листьев: " << n << " (каждый лист [i,i] соответствует одному числу)\n";

    cout << "Максимум: " << queryMax(root, 0, n - 1) << endl;
    cout << "Минимум: " << queryMin(root, 0, n - 1) << endl;
    cout << "Сумма: " << querySum(root, 0, n - 1) << endl;
    cout << "Нечётных чисел: " << queryOdd(root, 0, n - 1) << endl;
    cout << "Чётных чисел: " << queryEven(root, 0, n - 1) << endl;

    cout << "\nПример обновления: меняем элемент с индексом 0 на 999\n";
    update(root, 0, 999);
    cout << "Новый максимум: " << queryMax(root, 0, n - 1) << endl;
    cout << "Новый минимум: " << queryMin(root, 0, n - 1) << endl;
    cout << "Новая сумма: " << querySum(root, 0, n - 1) << endl;

    cout << "\nСТРУКТУРА ДЕРЕВА ОТРЕЗКОВ:\n";
    cout << "================================\n";
    printTree(root);
    cout << "================================\n";

    deleteTree(root);

    return 0;
}