Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Медленное дерево отрезков - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Посчитать приблизительное значение функции sin по заданной формуле http://www.cyberforum.ru/cpp-beginners/thread1507002.html
Дальше решаю задачник Абрамяна через c++ Пришел на 23. Вот мое решение: #include <iostream> #include <conio.h> #include <math.h> using namespace std; double fact(int n) { int i,b=1; for...
C++ Чтение CSV-файла в двумерный массив Есть файл вида:"TEXT,1,20140729,150700,73.3500000,73.5800000,73.3500000,73.4800000,2301260"Нужно собрать числа в двумерный массив. Количество строк в файле неизвестно. Попробовал использовать... http://www.cyberforum.ru/cpp-beginners/thread1506970.html
Не понимаю, какие в моем коде ошибки C++
#include <iostream> char board = {'-','-','-','-','-','-','-','-','-',}; int get_move(){ std::cout <<"Move options:" << std::endl; std::cout <<"-7-|-8-|-9-" << std::endl; std::cout...
Vector iterator not incrementable C++
Здравствуйте. Подскажите, из-за чего не работает код? При запуске программы появляется ошибка: "... expression: vector iterator not incrementable ..." #include <iostream> #include <vector>...
C++ Заполнить массив неодинаковыми случайными числами http://www.cyberforum.ru/cpp-beginners/thread1506952.html
нужно дополнить ф-кцию рандома так что бы заполнить массив не одинаковыми числами. Как прописать возвращение на внутренний цыкл, чтобы сново проверить выданный рандом?? #include <iostream> #include...
C++ Задача по теме "Функции с переменным числом параметров" Задание: Ввести функцию с переменным числом параметров как функцию класса. Цель функции — инициализация элементов класса (расширение метода ввода). В качестве параметров передавать значения... подробнее

Показать сообщение отдельно
cat4xan
0 / 0 / 1
Регистрация: 30.07.2015
Сообщений: 2

Медленное дерево отрезков - C++

30.07.2015, 09:08. Просмотров 229. Ответов 2
Метки (Все метки)

Приветствую. Пишу дерево отрезков для задачи нахождения сумм на отрезках. Оно работает, даже вроде правильно, но при массиве 105 и количестве запросов 105 не укладывается в 1 секунду. Подскажите пожалуйста, как его можно ускорить, переписать, дописать. Код может вызвать шок!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<long long> a;
vector<long long> t;
const int neutralV = 0;
 
void build_tree()
{
    for (int i = a.size() - 1; i < 2 * a.size() - 1; i++)
        t[i] = a[i - (a.size() - 1)];
    for (int i = a.size() - 2; i >= 0; i--)
        t[i] = t[(i << 1) + 1] + t[(i << 1) + 2];
}
 
long long rsq(int v, int cl, int cr, int left, int right)
{
    if (left >= right)
        return neutralV;
    if (cl == left && cr == right)
        return t[v];
 
    int cm = (cl + cr) >> 1;
    long long neutral = neutralV;
    neutral += rsq((v << 1) + 1, cl, cm, left, min(cm, right));
    neutral += rsq((v << 1) + 2, cm, cr, max(left, cm), right);
    return neutral;
}
 
int main()
{
    // freopen("input.in", "r", stdin);
    int n;
    cin >> n;
    int old_n = n;
    n = 2 << ((int)(log2(n) + 0.99999999) - 1);
    a.assign(n, neutralV);
    t.assign(2 * n - 1, neutralV);
    for (int i = 0; i < old_n; i++)
    {
        cin >> a[i];
    }
    build_tree();
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        int left, right;
        cin >> left >> right;
        left--;
        cout << rsq(0, 0, n, left, right) << " ";
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru