不开 O2 T 7 个点，开了 O2 M 4 个点

import Control.Monad
import Data.List

data Segtree = Leaf Int | Node Int Int Segtree Segtree deriving Show
--                  val        len sum ls      rs

query :: Int -> Int -> Segtree -> Int
query l r (Leaf x)
  | l <= 0 && r > 0 = x
  | otherwise       = 0
query l r (Node n s ls rs)
  | l <= 0 && r >= n = s
  | r <= 0 || l >= n = 0
  | otherwise        = let m = n `div` 2 in (query l r ls) + query (l - m) (r - m) rs

modify :: Int -> Int -> Int -> Segtree -> Segtree
modify l r k (Leaf x)
  | l <= 0 && r > 0 = Leaf (x + k)
  | otherwise       = Leaf x
modify l r k (Node n s ls rs)
  | r <= 0 || l >= n = Node n s ls rs
  | otherwise        = let m = n `div` 2
                           s' = s + k * (min n r - max l 0)
                           ls' = modify l r k ls
                           rs' = modify (l - m) (r - m) k rs
                       in Node n s' ls' rs'

build :: [Int] -> Segtree
build [x] = Leaf x
build l = Node n s ls rs where
    n = length l
    m = n `div` 2
    (a, b) = splitAt m l
    ls = build a
    rs = build b
    s = query 0 m ls + query 0 (n - m) rs

solve :: [Int] -> [[Int]] -> [Int]
solve l = reverse . fst . foldl' (
    \(ans, st) q -> case q of
        [1, l, r, k] -> (ans, modify (l - 1) r k st)
        [2, l, r] -> (query (l - 1) r st : ans, st)) ([], build l)

readMult :: (Read a) => IO [a]
readMult = do
    s <- getLine
    return (map read (words s))

main :: IO ()
main = do
    [n, q] <- readMult :: IO [Int]
    l <- readMult :: IO [Int]
    qs <- replicateM q (readMult :: IO [Int])
    let anss = solve l qs
    forM_ anss $ \n -> do
        print n