I made a segment tree with python, so I will introduce it

Introduction

There are many other articles about segment trees, so please choose the one that is easy for you to use! (If you like the segment tree in this article, please use it for competitive programming etc. It is welcome.)

Reference article

https://algo-logic.info/segment-tree/ https://qiita.com/takayg1/items/c811bd07c21923d7ec69 https://qiita.com/mosamosa/items/d17ab5af6e19f67202cb

Code introduction

Introducing today is a mode that allows you to select a segment tree function. Code below (Received comments on 2021/1/13 and revised if enumeration → dictionary)

segki_simple.py


import sys
import math
sys.setrecursionlimit(10**7)

class segki():
    DEFAULT = {
        'min': 1 << 60,
        'max': -(1 << 60),
        'sum': 0,
        'prd': 1,
        'gcd': 0,
        'lmc': 1,
        '^': 0,
        '&': (1 << 60) - 1,
        '|': 0,
    }

    FUNC = {
        'min': min,
        'max': max,
        'sum': (lambda x, y: x + y),
        'prd': (lambda x, y: x * y),
        'gcd': math.gcd,
        'lmc': (lambda x, y: (x * y) // math.gcd(x, y)),
        '^': (lambda x, y: x ^ y),
        '&': (lambda x, y: x & y),
        '|': (lambda x, y: x | y),
    }

    def __init__(self, N, ls, mode='min'):
        """
Number of leaves N,Element ls,Function mode(min,max,sum,prd(product),gcd,lmc,^,&,|)
        """
        self.default = self.DEFAULT[mode]
        self.func = self.FUNC[mode]
        self.N = N
        self.K = (N - 1).bit_length()
        self.N2 = 1 << self.K
        self.dat = [self.default] * (2**(self.K + 1))
        for i in range(self.N):  #Leaf construction
            self.dat[self.N2 + i] = ls[i]
        self.build()

    def build(self):
        for j in range(self.N2 - 1, -1, -1):
            self.dat[j] = self.func(self.dat[j << 1], self.dat[j << 1 | 1])  #Conditions that parents have

    def leafvalue(self, x):  #The xth value in the list
        return self.dat[x + self.N2]

    def update(self, x, y):  # index(x)To y
        i = x + self.N2
        self.dat[i] = y
        while i > 0:  #Change parent value
            i >>= 1
            self.dat[i] = self.func(self.dat[i << 1], self.dat[i << 1 | 1])
        return

    def query(self, L, R):  # [L,R)Section acquisition
        L += self.N2
        R += self.N2
        vL = self.default
        vR = self.default
        while L < R:
            if L & 1:
                vL = self.func(vL, self.dat[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.dat[R], vR)
            L >>= 1
            R >>= 1
        return self.func(vL, vR)

I think that the monoids that can be placed on the segment tree are mostly covered (min, max, sum, product, gcd, lmc, ^, &, |). Please point out any mistakes.

Explanation

Tree construction

There are three arguments required to build a tree: number of elements N, initial element (list), and function (mode). The identity element is defined in DEFAULT (change if necessary). Computational complexity O (N)

Update value

Specify the index to be changed by update and the changed value. Computational complexity O (log (N))

Get value

You can get the value of any index with leafvalue. Computational complexity O (1). (For example, it is possible to add x to the kth value in combination with updating the value.)

Get the value of the interval

You can get the value of the interval with query. query (L, R) The value that can be obtained is the value of the interval [L, R). Computational complexity O (log (N))

Example of use

1, atcoder ABC185F https://atcoder.jp/contests/abc185/tasks/abc185_f https://atcoder.jp/contests/abc185/submissions/19042056 It's an xor guy. About 900ms. There seems to be more room for improvement ...

2, atcoder Chokudai SpeedRun 001J https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_j https://atcoder.jp/contests/chokudai_S001/submissions/19404893 It is a problem to find the number of inversions. You can use sum.

3, atcoder Chokudai SpeedRun 001H https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_h https://atcoder.jp/contests/chokudai_S001/submissions/19404925 It's a LIS problem. You can use max.

in conclusion

Thank you for reading. I myself am a beginner in competitive programming, so please point out any mistakes. Let's enjoy the competitive professional life together! !!

Recommended Posts

I made a segment tree with python, so I will introduce it
I made a daemon with Python
I made a character counter with Python
I made a Hex map with Python
I made a roguelike game with Python
I made a simple blackjack with Python
I made a configuration file with Python
I made a neuron simulator with Python
I made a competitive programming glossary with Python
I made a weather forecast bot-like with Python.
I made a GUI application with Python + PyQt5
I made a Twitter fujoshi blocker with Python ①
[Python] I made a Youtube Downloader with Tkinter.
I made a bin picking game with Python
I made a Mattermost bot with Python (+ Flask)
I tried to make a calculator with Tkinter so I will write it
I made a Twitter BOT with GAE (python) (with a reference)
I made blackjack with python!
I made a net news notification app with Python
I made a Python3 environment on Ubuntu with direnv.
Every time I draw a graph with python, I check it, so I will summarize only the simplest usage
I made a LINE BOT with Python and Heroku
I customized it with Visual Studio Code (mainly for python), so I will summarize it
I made blackjack with Python.
I made wordcloud with Python.
When I made a treemap (area graph) with python, it was subtle, so when I used flourish, it felt pretty good.
A Python beginner made a chat bot, so I tried to summarize how to make it.
I made a simple typing game with tkinter in Python
I made a package to filter time series with python
I made a simple book application with python + Flask ~ Introduction ~
I made a puzzle game (like) with Tkinter in Python
I made a Line-bot using Python!
[Python] I made a function that decrypts AES encryption just by throwing it with pycrypto.
I made a server with Python socket and ssl and tried to access it from a browser
Life game with Python [I made it] (on the terminal & Tkinter)
I made a simple circuit with Python (AND, OR, NOR, etc.)
I made a library to easily read config files with Python
I made a package that can compare morphological analyzers with Python
W3C Validators didn't work with Sublime Text3 so I made it work
I made a Nyanko tweet form with Python, Flask and Heroku
I made a lot of files for RDP connection with Python
[Python] I made an image viewer with a simple sorting function.
I made a shuffle that can be reset (reverted) with Python
Homework was a pain, so I do management accounting with Python
I made a poker game server chat-holdem using websocket with python
[python] I made a class that can write a file tree quickly
I made a chatbot with Tensor2Tensor and this time it worked
I made a payroll program in Python!
I touched "Orator" so I made a note
I drew a heatmap with seaborn [Python]
I tried a functional language with Python
I researched Docker, so I will summarize it
I made a life game with Numpy
I made a stamp generator with GAN
After studying Python3, I made a Slackbot
I made a WEB application with Django
2. Make a decision tree from 0 with Python and understand it (2. Python program basics)
I want to do it with Python lambda Django, but I will stop
I made a tool to automatically browse multiple sites with Selenium (Python)
I tried to discriminate a 6-digit number with a number discrimination application made with python
[Streamlit] I hate JavaScript, so I make a web application only with Python