트라이와 구간 트리의 문제 분할 방식

트라이와 구간 트리는 둘 다 트리지만, 푸는 문제 축이 다릅니다. 트라이는 문자열의 글자 경로를 따라가고, 구간 트리는 인덱스 범위를 쪼개서 관리합니다. 겉모양이 아니라 무엇을 기준으로 분할하느냐가 선택 관점입니다.

두 구조를 헷갈리면 구현은 길어지고 성능도 불안정해집니다. 이 파트는 두 구조를 한 장에서 비교해, 어떤 문제에서 무엇을 선택할지 빠르게 판단하도록 구성했습니다. 설명은 쉽게 풀되 코테 실전에 필요한 질의 복잡도 관점은 그대로 유지합니다.

핵심 패턴 정돈

트라이와 구간 트리의 차이는 모양이 아니라 분할 기준에서 시작됩니다. 문제를 읽을 때 우선 문자열 축인지, 인덱스 구간 축인지 표시하고 아래를 비교해 보세요.

분할 기준은 데이터를 어떤 축으로 쪼개 노드에 담을지 정하는 규칙입니다. 각 노드가 대표하는 상태 공간이 접두사인지 구간인지에 따라 자료구조가 달라집니다. 자동완성은 접두사 분할이 자연스럽고, 구간 합 질의는 인덱스 범위 분할이 자연스럽습니다.

트라이(Trie)는 문자열을 문자 경로로 저장하는 접두사 트리입니다. 간선이 문자이고 루트에서 노드까지의 경로가 하나의 접두사를 의미합니다. "cat"과 "car"는 c -> a 경로를 공유하기 때문에 접두사 연산에서 효율적입니다.

구간 트리(Segment Tree)는 배열 구간을 반씩 나눠 집계값을 저장하는 구조입니다. [l, r] 범위를 이진 분할하고 각 노드에 합/최댓값 같은 집계 함수를 유지합니다. 예를 들어 [0,7] 합을 루트에 두고 자식에 [0,3], [4,7] 합을 저장하면 구간 질의를 빠르게 처리할 수 있습니다.

트라이/구간트리 실전 장애와 연결하기

문제 유형과 맞지 않는 구조를 선택하면 구현은 복잡해지고 성능은 나빠집니다.
예를 들어 자동완성 문제를 구간 트리로 풀면 모델 자체가 맞지 않습니다.

반대로 구간 합 질의를 트라이로 풀려 하면 상태 표현이 비효율적입니다.
우선 질의 축(문자열 경로 vs 인덱스 구간)을 파악해야 합니다.

질의/업데이트 테스트로 빠르게 검증하기

학습 효율을 높이려면 오답 -> 디버깅 -> 교정 -> 검증 순서로 로그를 남기면서 진행하는 것이 가장 빠릅니다.

문제 축에 따라 구조가 달라지는 과정을 간단히 비교합니다.

문자열 질의: "car" 존재 여부, "ca" 접두사 여부
수열 질의: 인덱스 [l, r] 구간 합

문자열은 문자 경로를 따라 내려가므로 트라이가 자연스럽습니다.
구간 합은 인덱스 범위를 분할해 집계하므로 세그먼트 트리가 적합합니다.
질의 축을 잘못 잡으면 구현은 복잡해지고 성능도 떨어집니다.

트라이/세그트리: 트라이 기본 연산

문제 의도: 트라이에서 삽입/완전검색/접두사검색 기본 연산을 확인합니다.
입력 예시: insert("cat","car"), search("car"), startsWith("ca")
출력 예시: true, true insert는 문자 단위로 노드를 따라가며 없으면 새 노드를 만드는 방식입니다.

main.cpp

#include <iostream>
#include <memory>
#include <string>
#include <unordered_map>
using namespace std;

struct TrieNode {
    unordered_map<char, unique_ptr<TrieNode>> children;
    bool end = false;
};

class Trie {
private:
    TrieNode root;
public:
    void insert(const string& word) {
        TrieNode* cur = &root;
        for (char ch : word) {
            if (!cur->children.count(ch)) {
                cur->children[ch] = make_unique<TrieNode>();
            }
            cur = cur->children[ch].get();
        }
        cur->end = true;
    }

    bool startsWith(const string& prefix) const {
        const TrieNode* cur = &root;
        for (char ch : prefix) {
            auto it = cur->children.find(ch);
            if (it == cur->children.end()) return false;
            cur = it->second.get();
        }
        return true;
    }

    bool search(const string& word) const {
        const TrieNode* cur = &root;
        for (char ch : word) {
            auto it = cur->children.find(ch);
            if (it == cur->children.end()) return false;
            cur = it->second.get();
        }
        return cur->end;
    }
};

int main() {
    Trie trie;
    for (const string& w : {"cat", "car", "care", "dog"}) trie.insert(w);
    cout << boolalpha << trie.startsWith("ca") << "\n";
    cout << boolalpha << trie.search("car") << "\n";
    cout << boolalpha << trie.search("cap") << "\n";
    return 0;
}

Main.java

import java.util.HashMap;
import java.util.Map;

public class Main {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean end = false;
    }

    static class Trie {
        TrieNode root = new TrieNode();

        void insert(String word) {
            TrieNode cur = root;
            for (char ch : word.toCharArray()) {
                cur.children.putIfAbsent(ch, new TrieNode());
                cur = cur.children.get(ch);
            }
            cur.end = true;
        }

        boolean startsWith(String prefix) {
            TrieNode cur = root;
            for (char ch : prefix.toCharArray()) {
                if (!cur.children.containsKey(ch)) return false;
                cur = cur.children.get(ch);
            }
            return true;
        }

        boolean search(String word) {
            TrieNode cur = root;
            for (char ch : word.toCharArray()) {
                if (!cur.children.containsKey(ch)) return false;
                cur = cur.children.get(ch);
            }
            return cur.end;
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        for (String w : new String[]{"cat", "car", "care", "dog"}) trie.insert(w);
        System.out.println(trie.startsWith("ca"));
        System.out.println(trie.search("car"));
        System.out.println(trie.search("cap"));
    }
}

main.py

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()
            cur = cur.children[ch]
        cur.end = True

    def starts_with(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True

    def search(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return cur.end

trie = Trie()
for w in ["cat", "car", "care", "dog"]:
    trie.insert(w)
print(trie.starts_with("ca"))  # True
print(trie.search("car"))      # True
print(trie.search("cap"))      # False

main.rs

use std::collections::HashMap;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, TrieNode>,
    end: bool,
}

#[derive(Default)]
struct Trie {
    root: TrieNode,
}

impl Trie {
    fn insert(&mut self, word: &str) {
        let mut cur = &mut self.root;
        for ch in word.chars() {
            cur = cur.children.entry(ch).or_default();
        }
        cur.end = true;
    }

    fn starts_with(&self, prefix: &str) -> bool {
        let mut cur = &self.root;
        for ch in prefix.chars() {
            if let Some(next) = cur.children.get(&ch) {
                cur = next;
            } else {
                return false;
            }
        }
        true
    }

    fn search(&self, word: &str) -> bool {
        let mut cur = &self.root;
        for ch in word.chars() {
            if let Some(next) = cur.children.get(&ch) {
                cur = next;
            } else {
                return false;
            }
        }
        cur.end
    }
}

fn main() {
    let mut trie = Trie::default();
    for w in ["cat", "car", "care", "dog"] {
        trie.insert(w);
    }
    println!("{}", trie.starts_with("ca"));
    println!("{}", trie.search("car"));
    println!("{}", trie.search("cap"));
}

트라이/구간 트리 동작 트리 구조 조건 검토

트라이는 문자 하나당 한 단계씩 내려가는 구조입니다.
접두사가 같은 단어는 경로를 공유해 검색/접두사 판정이 빠릅니다.
자동완성, 사전 검색, 금칙어 탐지 등 문자열 prefix 문제에서 강점을 가집니다.

평균 시간복잡도: O(L) (L은 문자열 길이)
최악 시간복잡도: O(L)
공간복잡도: 저장된 전체 문자 수에 비례

트라이/세그트리: 구간 트리 합 질의

문제 의도: 세그먼트 트리로 구간 합 질의를 O(log N)에 처리합니다.
입력 예시: 배열 [2,1,3,4,5], 질의 [1,3], [0,4]
출력 예시: 8, 15 트리 노드마다 구간 합을 저장해 두고, 필요한 구간만 방문해 답을 합칩니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
private:
    int n;
    vector<int> tree;

    void build(int node, int l, int r, const vector<int>& nums) {
        if (l == r) {
            tree[node] = nums[l];
            return;
        }
        int mid = (l + r) / 2;
        build(node * 2, l, mid, nums);
        build(node * 2 + 1, mid + 1, r, nums);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    int queryInner(int node, int l, int r, int ql, int qr) const {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return queryInner(node * 2, l, mid, ql, qr) +
               queryInner(node * 2 + 1, mid + 1, r, ql, qr);
    }

public:
    explicit SegmentTree(const vector<int>& nums) {
        n = static_cast<int>(nums.size());
        tree.assign(4 * n, 0);
        build(1, 0, n - 1, nums);
    }

    int query(int l, int r) const { return queryInner(1, 0, n - 1, l, r); }
};

int main() {
    SegmentTree seg({2, 1, 3, 4, 5});
    cout << seg.query(1, 3) << "\n";
    cout << seg.query(0, 4) << "\n";
    return 0;
}

Main.java

public class Main {
    static class SegmentTree {
        int n;
        int[] tree;

        SegmentTree(int[] nums) {
            n = nums.length;
            tree = new int[4 * n];
            build(1, 0, n - 1, nums);
        }

        void build(int node, int l, int r, int[] nums) {
            if (l == r) {
                tree[node] = nums[l];
                return;
            }
            int mid = (l + r) / 2;
            build(node * 2, l, mid, nums);
            build(node * 2 + 1, mid + 1, r, nums);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }

        int query(int ql, int qr) {
            return queryInner(1, 0, n - 1, ql, qr);
        }

        int queryInner(int node, int l, int r, int ql, int qr) {
            if (qr < l || r < ql) return 0;
            if (ql <= l && r <= qr) return tree[node];
            int mid = (l + r) / 2;
            return queryInner(node * 2, l, mid, ql, qr) +
                   queryInner(node * 2 + 1, mid + 1, r, ql, qr);
        }
    }

    public static void main(String[] args) {
        SegmentTree seg = new SegmentTree(new int[]{2, 1, 3, 4, 5});
        System.out.println(seg.query(1, 3));
        System.out.println(seg.query(0, 4));
    }
}

main.py

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        self._build(1, 0, self.n - 1, nums)

    def _build(self, node, l, r, nums):
        if l == r:
            self.tree[node] = nums[l]
            return
        mid = (l + r) // 2
        self._build(node * 2, l, mid, nums)
        self._build(node * 2 + 1, mid + 1, r, nums)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query(self, ql, qr):
        return self._query(1, 0, self.n - 1, ql, qr)

    def _query(self, node, l, r, ql, qr):
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return self._query(node * 2, l, mid, ql, qr) + self._query(node * 2 + 1, mid + 1, r, ql, qr)

seg = SegmentTree([2, 1, 3, 4, 5])
print(seg.query(1, 3))  # 8
print(seg.query(0, 4))  # 15

main.rs

struct SegmentTree {
    n: usize,
    tree: Vec<i32>,
}

impl SegmentTree {
    fn new(nums: &[i32]) -> Self {
        let n = nums.len();
        let mut seg = Self {
            n,
            tree: vec![0; 4 * n],
        };
        seg.build(1, 0, n - 1, nums);
        seg
    }

    fn build(&mut self, node: usize, l: usize, r: usize, nums: &[i32]) {
        if l == r {
            self.tree[node] = nums[l];
            return;
        }
        let mid = (l + r) / 2;
        self.build(node * 2, l, mid, nums);
        self.build(node * 2 + 1, mid + 1, r, nums);
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1];
    }

    fn query(&self, ql: usize, qr: usize) -> i32 {
        self.query_inner(1, 0, self.n - 1, ql, qr)
    }

    fn query_inner(&self, node: usize, l: usize, r: usize, ql: usize, qr: usize) -> i32 {
        if qr < l || r < ql {
            return 0;
        }
        if ql <= l && r <= qr {
            return self.tree[node];
        }
        let mid = (l + r) / 2;
        self.query_inner(node * 2, l, mid, ql, qr)
            + self.query_inner(node * 2 + 1, mid + 1, r, ql, qr)
    }
}

fn main() {
    let seg = SegmentTree::new(&[2, 1, 3, 4, 5]);
    println!("{}", seg.query(1, 3));
    println!("{}", seg.query(0, 4));
}

트라이/구간 트리 동작 순회 상태 추적

구간 트리는 인덱스 구간을 절반씩 나누어 집계 값을 저장합니다.
질의 구간과 겹치는 노드만 방문하므로 전체 선형 탐색보다 효율적입니다.
구간 합, 구간 최소/최대, 구간 업데이트 문제에서 표준 해법으로 사용됩니다.

평균 시간복잡도: 질의 O(log N)
최악 시간복잡도: 질의 O(log N)
공간복잡도: O(N)

트라이/세그트리: 점 업데이트 포함

문제 의도: 세그먼트 트리에서 점 업데이트 후 질의 결과가 즉시 반영되는지 확인합니다.
입력 예시: 배열 [2,1,3,4,5], update(2,10) 후 구간 질의
출력 예시: 업데이트 전/후 구간 합 변화 update는 리프 값을 바꾸고, 돌아오면서 부모 합을 다시 계산하는 방식입니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
public:
    int n;
    vector<int> tree;
    explicit SegmentTree(const vector<int>& nums) {
        n = static_cast<int>(nums.size());
        tree.assign(4 * n, 0);
        build(1, 0, n - 1, nums);
    }
    void build(int node, int l, int r, const vector<int>& nums) {
        if (l == r) {
            tree[node] = nums[l];
            return;
        }
        int mid = (l + r) / 2;
        build(node * 2, l, mid, nums);
        build(node * 2 + 1, mid + 1, r, nums);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    int query(int node, int l, int r, int ql, int qr) const {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return query(node * 2, l, mid, ql, qr) + query(node * 2 + 1, mid + 1, r, ql, qr);
    }
    void update(int node, int l, int r, int idx, int val) {
        if (idx < l || idx > r) return;
        if (l == r) {
            tree[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        update(node * 2, l, mid, idx, val);
        update(node * 2 + 1, mid + 1, r, idx, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
};

int main() {
    SegmentTree seg({2, 1, 3, 4, 5});
    seg.update(1, 0, seg.n - 1, 2, 10);
    cout << seg.query(1, 0, seg.n - 1, 1, 3) << "\n";
    return 0;
}

Main.java

public class Main {
    static class SegmentTree {
        int n;
        int[] tree;
        SegmentTree(int[] nums) {
            n = nums.length;
            tree = new int[4 * n];
            build(1, 0, n - 1, nums);
        }
        void build(int node, int l, int r, int[] nums) {
            if (l == r) {
                tree[node] = nums[l];
                return;
            }
            int mid = (l + r) / 2;
            build(node * 2, l, mid, nums);
            build(node * 2 + 1, mid + 1, r, nums);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
        int query(int node, int l, int r, int ql, int qr) {
            if (qr < l || r < ql) return 0;
            if (ql <= l && r <= qr) return tree[node];
            int mid = (l + r) / 2;
            return query(node * 2, l, mid, ql, qr) + query(node * 2 + 1, mid + 1, r, ql, qr);
        }
        void update(int node, int l, int r, int idx, int val) {
            if (idx < l || idx > r) return;
            if (l == r) {
                tree[node] = val;
                return;
            }
            int mid = (l + r) / 2;
            update(node * 2, l, mid, idx, val);
            update(node * 2 + 1, mid + 1, r, idx, val);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

    public static void main(String[] args) {
        SegmentTree seg = new SegmentTree(new int[]{2, 1, 3, 4, 5});
        seg.update(1, 0, seg.n - 1, 2, 10);
        System.out.println(seg.query(1, 0, seg.n - 1, 1, 3));
    }
}

main.py

def update(seg, node, l, r, idx, val):
    if idx < l or idx > r:
        return
    if l == r:
        seg.tree[node] = val
        return

    mid = (l + r) // 2
    update(seg, node * 2, l, mid, idx, val)
    update(seg, node * 2 + 1, mid + 1, r, idx, val)
    seg.tree[node] = seg.tree[node * 2] + seg.tree[node * 2 + 1]

update(seg, 1, 0, seg.n - 1, 2, 10)
print(seg.query(1, 3))  # 15

main.rs

struct SegmentTree {
    n: usize,
    tree: Vec<i32>,
}

impl SegmentTree {
    fn new(nums: &[i32]) -> Self {
        let n = nums.len();
        let mut seg = Self {
            n,
            tree: vec![0; 4 * n],
        };
        seg.build(1, 0, n - 1, nums);
        seg
    }

    fn build(&mut self, node: usize, l: usize, r: usize, nums: &[i32]) {
        if l == r {
            self.tree[node] = nums[l];
            return;
        }
        let mid = (l + r) / 2;
        self.build(node * 2, l, mid, nums);
        self.build(node * 2 + 1, mid + 1, r, nums);
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1];
    }

    fn query(&self, node: usize, l: usize, r: usize, ql: usize, qr: usize) -> i32 {
        if qr < l || r < ql {
            return 0;
        }
        if ql <= l && r <= qr {
            return self.tree[node];
        }
        let mid = (l + r) / 2;
        self.query(node * 2, l, mid, ql, qr) + self.query(node * 2 + 1, mid + 1, r, ql, qr)
    }

    fn update(&mut self, node: usize, l: usize, r: usize, idx: usize, val: i32) {
        if idx < l || idx > r {
            return;
        }
        if l == r {
            self.tree[node] = val;
            return;
        }
        let mid = (l + r) / 2;
        self.update(node * 2, l, mid, idx, val);
        self.update(node * 2 + 1, mid + 1, r, idx, val);
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1];
    }
}

fn main() {
    let mut seg = SegmentTree::new(&[2, 1, 3, 4, 5]);
    seg.update(1, 0, seg.n - 1, 2, 10);
    println!("{}", seg.query(1, 0, seg.n - 1, 1, 3));
}