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! !!