Дерево отрезков на сумму

@NebraskKrasnod · Регистрация: 16.04.2022

Студворк — интернет-сервис помощи студентам

В этой задаче вам нужно написать обычное дерево отрезков на сумму.

Входные данные:
Первая строка содержит два числа n и m (1≤n,m≤100000) — размер массива и число операций. Следующая строка содержит n чисел ai — начальное состояние массива (0≤ai≤109). Далее следует описание операций. Описание каждой операции имеет следущий вид:

1 i v — присвоить элементу с индексом i значение v (0≤i<n, 0≤v≤109).
2 l r — вычислить сумму элементов с индексами от l до r−1 (0≤l<r≤n).

Выходные данные:
Для каждой операции второго типа выведите соответствующую сумму.

Пример:
входные данные
5 5
5 4 2 3 5
2 0 3
1 1 1
2 0 3
1 3 1
2 0 5
выходные данные
11
8
14

@Пифагор · 24.04.2022, 21:00

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ql, qo = map( int, input('n, m = ').split() )
lst = list( map( int, input('Список = ').split() ) )
i = ql
res = []
 
while i:
    a, b, c = map( int, input('Операция: ').split() )
    if a not in (1, 2):
        print('Неизвестный тип операции')
    else:
        if a == 1:
            lst[b] = c
        elif a == 2:
            res.append(sum(lst[b:c]))
        i-=1
 
list( map( print, res ) )

@eaa · 24.04.2022, 21:32

дерево отрезков тогда тут причем?

@Пифагор · 24.04.2022, 21:38

eaa, тут одному пробелы на таб надо было заменить без "регулятора строк", а Вы удивляетесь, причем тут дерево отрезков

@eaa · 24.04.2022, 21:42

Пифагор, а где в решении дерево отрезков?

Добавлено через 43 секунды
Научиться хочу, чтобы знать на будущее.

@Пифагор · 24.04.2022, 21:48

eaa, если честно, я даже не заморачивался, просто сделал по ТЗ и проверил верность результатов из примеров входных и выходных данных.

@eaa · 24.04.2022, 21:54

Ваше решение O(n*m). При больших n и m - это 10¹⁰.
А правильное решение O(m*log(n)).

@idealist · 26.04.2022, 02:40

Добавлено через 41 минуту

Сообщение от eaa

правильное решение O(m*log(n))

Ну да, такое примерно:

Python
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
from math import log2
from math import ceil
from operator import add
#==============================================================================
def get_parent_ind_and_is_R(ind):
    return divmod( ind, 2 )
#==============================================================================
def update_parent_and_get_parent_ind(tree, ind, fun):
    parent_ind, is_R = get_parent_ind_and_is_R(ind)
    if is_R:
        tree[parent_ind] = fun( tree[ind - 1], tree[ind] )
    else:
        tree[parent_ind] = fun( tree[ind], tree[ind + 1] )
    return parent_ind
#==============================================================================
def update_all_parents(tree, ind, fun):
    while ind > 1:
        ind = update_parent_and_get_parent_ind(tree, ind, fun)
#==============================================================================
def fill_tree(tree, fun):
    for i in range( len(tree)-1, 2, -2 ):
        update_parent_and_get_parent_ind(tree, i, fun)
#==============================================================================
def tree_ind_from_arr_ind(tree, ind):
    return len(tree)//2 + ind
#==============================================================================
def set_leaf_and_update_parents( tree, ind, val, fun ):
    tree_ind = tree_ind_from_arr_ind(tree, ind)
    tree[ tree_ind ] = val
    update_all_parents(tree, tree_ind, fun)
#==============================================================================
def is_R(ind):
    return ind % 2
#==============================================================================
def get_fun_for_segm( tree, L, R, fun, empty_val_for_fun ):
    res = empty_val_for_fun
    L   = tree_ind_from_arr_ind(tree, L)
    R   = tree_ind_from_arr_ind(tree, R)
    while L <= R:
        if is_R(L):
            res = fun(res, tree[L])
        if not is_R(R):
            res = fun(res, tree[R])
        L = L+1 >> 1
        R = R-1 >> 1
    return res
#==============================================================================
def exec_ops( tree, ops, fun, empty_val_for_fun ):
    for op in ops:
        a, b, c = op
        if a == 1:
            ind = b
            val = c
            set_leaf_and_update_parents(tree, ind, val, fun)
        else:
            L_arr_ind = b
            segm_len  = c
            print( get_fun_for_segm( tree, L_arr_ind, segm_len-1, fun, empty_val_for_fun ) )
#==============================================================================
n, m = map( int, input( 'n, m = ' ).split() )
lis  = list( map( int, input( 'array = ' ).split() ) )
n_2  = 1 << ceil( log2(n) )
empty_val_for_add = 0
tree = [0]*n_2 + lis + [ empty_val_for_add ]*(n_2 - n)
fill_tree( tree, add )
ops  = []
for _ in range(m):
    ops.append( tuple( map( int, input( 'a,b,c = ' ).split() ) ) )
exec_ops( tree, ops, add, empty_val_for_add )

@idealist · 27.04.2022, 00:56

def

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139

	Дерево отрезков на сумму 24.04.2022, 20:19. Показов 2929. Ответов 8 Метки нет (Все метки) В этой задаче вам нужно написать обычное дерево отрезков на сумму. Входные данные: Первая строка содержит два числа n и m (1≤n,m≤100000) — размер массива и число операций. Следующая строка содержит n чисел ai — начальное состояние массива (0≤ai≤109). Далее следует описание операций. Описание каждой операции имеет следущий вид: 1 i v — присвоить элементу с индексом i значение v (0≤i<n, 0≤v≤109). 2 l r — вычислить сумму элементов с индексами от l до r−1 (0≤l<r≤n). Выходные данные: Для каждой операции второго типа выведите соответствующую сумму. Пример: входные данные 5 5 5 4 2 3 5 2 0 3 1 1 1 2 0 3 1 3 1 2 0 5 выходные данные 11 8 14 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.04.2022, 21:32
	дерево отрезков тогда тут причем? 0

@Пифагор 2172 / 1655 / 840 Регистрация: 10.01.2015 Сообщений: 5,207
	24.04.2022, 21:38
	eaa, тут одному пробелы на таб надо было заменить без "регулятора строк", а Вы удивляетесь, причем тут дерево отрезков 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.04.2022, 21:42
	Пифагор, а где в решении дерево отрезков? Добавлено через 43 секунды Научиться хочу, чтобы знать на будущее. 0

@Пифагор 2172 / 1655 / 840 Регистрация: 10.01.2015 Сообщений: 5,207
	24.04.2022, 21:48
	eaa, если честно, я даже не заморачивался, просто сделал по ТЗ и проверил верность результатов из примеров входных и выходных данных. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.04.2022, 21:54
	Ваше решение O(nm). При больших n и m - это 10¹⁰. А правильное решение O(mlog(n)). 0

@idealist 3750 / 1944 / 612 Регистрация: 21.11.2021 Сообщений: 3,706
	27.04.2022, 00:56
	def 0

Опции темы

Дерево отрезков на сумму

Решение