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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Nebel
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12
#1

Дерево отрезков, редактирование куска и поиск суммы - C++

19.06.2013, 19:49. Просмотров 1257. Ответов 2
Метки нет (Все метки)

Добрый вечер.
Пишу алгоритм нахождения суммы элементов на отрезке и редактирования элементов на отрезке.
Вводится N - число элементов в массиве, K - кол - во операций.
Далее на вход программе дается 2 различные команды
A l r x - присвоить элементам с позиции l до r значение х
Q l r - найти сумму элементов на отрезке от l до r
Изначально массив заполнен нулями.
(1 <= N <= 100 000), (0 <= K <= 100 000).

Пример:
IN
5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5

OUT
3
2
3
4
2
7

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <cstring>
 
using namespace std;
 
int a[100000], N;
long long t[1000000];
 
void push(int x)
{
     if (t[x] != -1)
     {     
           t[2 * x] = t[2 * x + 1] = t[x];
           t[x] = -1;
     }
}
 
void update(int x, int l, int r, int L, int R, int c)
{
     if ((l > r) || (l > R) || (r < L))
        return;
        
     if ((L <= l) && (r <= R))
            t[x] = c;
     else
     {   
         push(x);
        // BUG         
        int mid = (l + r) / 2;   
        update(x * 2, l, mid, L, R, c);
        update(x * 2 + 1, mid + 1, r, L, R, c);
     }
}
 
long long sum(int x, int l, int r, int L, int R)
{
    if ((l > r) || (l > R) || (r < L))
       return 0;
       
    if ((L <= l) && (r <= R))
       return t[x];
    
    push(x);   
    int mid = (l + r) / 2;
    return sum(2 * x, l, mid, L, R) + sum(2 * x + 1, mid + 1, r, L, R);    
}
 
int main(void)
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    int N = 1, n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
            cin >> a[i];
            
    while (N < n)
          N *= 2;
      
    for(int i = 0; i < n; i++)
            t[N + i] = a[i];
    
    for(int i = n; i < N; i++)
            t[N + i] = 0;
               
    for(int i = N - 1; i >= 1; i--)
            t[i] = t[i * 2] + t[i * 2 + 1];
                         
    int x, y, z;
    char ss;
 
    for(int i = 0; i < k; i++)
    {       
            scanf ("%c", &ss);
            if (ss == 'A')
            {
                scanf("%d %d %d", &x, &y, &z);
                update(1, 1, N, x, y, z);  
            }
            else
            {
                scanf("%d %d", &x, &y);
                cout << sum(1, 1, N, x, y) << endl;
            }
    }       
    
    for(int i = 0; i < n; i++)
            cout << t[i] << " ";       
       
    fclose(stdin);
    fclose(stdout);
    return 0;
}
Не могу найти ошибку, пожалуйста помогите!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.06.2013, 19:49     Дерево отрезков, редактирование куска и поиск суммы
Посмотрите здесь:

C++ Поиск отрезков
C++ Бинарное дерево. Поиск.
C++ B-Дерево. Поиск. Вставка. Удаление.
Дерево отрезков C++
C++ На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков
Бинарное дерево, расчёт суммы элементов дерева C++
Дерево отрезков, проверьте код C++
Медленное дерево отрезков C++
C++ Есть ли у кого похожий алгоритм: распределения отрезков разной длины внутри отрезков фиксированной длины?
Дерево отрезков. Поиск суммы чисел на отрезке массива. Изменение всех чисел на отрезке массива C++
C++ Бинарное дерево: поиск суммы всех элементов

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
19.06.2013, 20:36     Дерево отрезков, редактирование куска и поиск суммы #2
я не смотрел ваш код, но решить данную задачу можно так:
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <functional>
 
using namespace std;
 
int main()
{
    ifstream com("commands.txt");
    ofstream out("output.txt");
 
    if (!com.good() || !out.good()) return -1;
 
    int v_size;
    int com_count;
    com >> v_size >> com_count;
    vector<int> v(v_size, 0);
 
    while (com_count-- > 0) {
        char c;
        com >> c;
        int from, to;
        com >> from >> to;
 
        if (to < from) swap(to, from);
        --from;
        switch ( c ) {
            case 'A':
                int x;
                com >> x;
                fill_n( begin(v) + from, to - from, x );
                break;
 
            case 'Q':
                out << accumulate( begin(v) + from,
                                    begin(v) + to, 0,
                                    plus<int>() ) << endl;
                break;
            default:
                cerr << "Command not found" << endl;
                return -1;
        }
    }
 
    com.close();
    out.close();
    return 0;
}
denysd21012011
3 / 3 / 2
Регистрация: 29.03.2013
Сообщений: 133
23.06.2014, 17:15     Дерево отрезков, редактирование куска и поиск суммы #3
Nebel, у нас с вами одна и та же проблема ( Дерево отрезков в определенной модификации ).... Вы куда-то еще пытались писать о помощи? И кстати, на каком ресурсе вы встретили эту задачу?
Yandex
Объявления
23.06.2014, 17:15     Дерево отрезков, редактирование куска и поиск суммы
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru