Блог пользователя peltorator

Автор peltorator, 4 года назад, По-русски

Привет!

Я продолжаю делать видео по алгоритмам, на этот раз тема более базовая. В этом видео я рассказываю про префиксные суммы и то, как с их помощью можно искать сумму на отрезке. Также вы сможете узнать, как легко обобщать префиксные суммы для двумерного, трехмерного, четырехмерного и т.д. случаев. Кроме этого, мы еще поговорим про такую простую концепцию как разностный массив, которая помогает очень легко решать задачи, в которых с первого взгляда хочется использовать всякие сложные структуры данных типа дерева отрезков. И в конце научимся прибавлять на отрезке в массива константы, арифметические прогрессии и даже квадратичные функции.

Ссылка на видео

Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями или идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!

Если вы еще не видели, можете также посмотреть мое видео про disjoint sparse table тут.

Codeforces группа с контестом

Реализации можно посмотреть по ссылкам:

Поиск одномерных префиксных сумм

Префиксные суммы на структурах для поиска суммы на отрезке

Поиск двумерных префиксных сумм двумя методами: раз, два

Поиск одномерного разностного массива

Разностный массив на структурах для прибавления на отрезке

  • Проголосовать: нравится
  • +365
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Для построения одномерных префиксных сумм/ксоров можно также использовать std::partial_sum: https://ideone.com/JttzK4

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    Да, точно, это классный C++ хак. Спасибо! Еще с ним всяких прикольных эффектов можно добиться, если использовать некоммутативную операцию.

»
4 года назад, # |
  Проголосовать: нравится +98 Проголосовать: не нравится

Roses are red, violets are blue, the blog is in English, then why not the video in English too?

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

3b1b vibes.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Love to watch your English channel.

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Love to watch your English channel.

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

If you can make a video in English then it would be more helpful for a larger audience.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

I rarely see such a well written code on this platform. Good job! Also great job for the tutorial, and please continue to make these in English because they are so good. And of course you will attract larger audience.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Wow! Manim in action. Are you using manim community version? Mind sharing the code?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No. I use vanilla manim. I saw that there are some cool features in the community version, but I didn't dive deep into it yet.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Большое спасибо за качественный материал,мне как начинающему было очень интересно и самое главное полезно,надеюсь вы будете продолжать свою образовательную деятельность.С нетерпением жду следуйщего урока)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Wow! I skimmed through parts of the video and this looks pure gold. I have linked this blog in one of the blogs I wrote on the same topic (albeit with some easier concepts) and one of the manim video editorials of a problem using this concept of difference array.

Keep creating!

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah, I used your blog post when I was preparing for this video. I also mentioned you at the end of my video and in the video description :)

    Thank you very much for your work!

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Oh, that's very nice to know when someone else builds upon your work. And thanks for the video mention, I just took a look :)

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Как же Сергей Орбитаев пиарится

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Wow, this is something I have been longing for unknowingly (Half closed Intervals mainly, I have seen pros use it and neal used it to solve problems in his streams of contest too).

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

thank you so much. I have solved Forest Queries problem using 2D prefix sum after watching your video. thank you again!!

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

In problem C, what's the form of the query?

l_1 r_1 l_2 r_2 l_3 r_3 l_4 r_4 l_5 r_5

or

l_1 l_2 l_3 l_4 l_5 r_1 r_2 r_3 r_4 r_5

if first one is the correct form, then how the answer for the second query is 32?